• 专利附录
  • 专利说明
  • 权利要求
  • 类似技术
  • 同族专利
  • 引用文献
  • 法律状态
  • 优先权
    • 专利摘要:

    公开号:WO1989003091A1
    申请号:PCT/JP1988/000971
    申请日:1988-09-22
    公开日:1989-04-06
    发明作者:Yusuke Mishina；Keiji Kojima
    申请人:Hitachi, Ltd.；
    IPC主号:G06F15-00
    专利说明:
    [0001] 明 棚 べ ク 卜 ルデー タ のソ ー 卜 方法お よびそれに好適なべ ク 卜 ルプ ロ セ ッサ 技術分野
    [0002] 本発明 はべ ク 卜 ルデー タ の ソ ー 卜 方法およびそれに好 適なべ ク 卜 ルプ ロ セ ッサに 関する 。
    [0003] 背景技術
    [0004] ソ ー 卜 又はマ ー ジ の よ う な非数値処理を ス カ ラプ ロ セ ッ サで実行す る と 、 そ の処理速度が遅い 。 こ の処理速度 向上の た め に 、 ベ ク ト ルプ ロ セ ッサを用 いて ソ ー ト の よ う な非数値処理を実行す る方法お よびそ の た め のべ ク 卜 ルプ ロ セ ッサが 、 本譲受人 に よ る米国特許出願 S N . 6 8 5 , 1 1 6 ( 1 9 8 4 , 1 2 , 2 1 出願 ） に 記載さ れ ている 。 ま た 、 その よ う な ベ ク ト ルプ ロ セ ッサ と し て 、 本譆受人 に よ り " M 6 8 0 H コ ン ピュ ー タ の 内蔵デ ー タ ベ ー スプ ロ セッサ " が販売さ れて いる 。
    [0005] 上記米国特許出願お よび上記 " 内蔵デ ー タ ベ ー スプ ロ セッサ " で は 、 ソ ー ト 処理のた めのソ ー ト 専用 ベ ク ト ル 命令お よびそ れで駆動 さ れるべ ク 卜 ルデ ー タ のソ ー 卜 の た めの回路を利用 する 。 一方 、 電子情報通信学会技術報 告 C O M P 8 6 — 8 8 ( P P 7 9 — 8 5 ) 記載の技術で は 、 従来の数値処理用 のベ ク ト ルプ ロ セ ッ サお よ びそ の た め に 用意さ れて い る基本的べ ク 卜 ル命令 、 た と えば 、 ベ ク ト ル移動命令 、 複数の 、 算術又は II理演算のた めの べ ク ト ル演算命令な どを利用 し て い る 。
    [0006] —設に 、 ベ ク ト ルプ ロ セ ッサは、 パイ プラ イ ン的に動 作する回路を用 いて 、 複数のベク ト ル要素を連続 して処 理する方法 （ ベ ク ト ル処理） に よ り 処理の高速化を図つ て いる 。 処理の高速化の ため に は異なるべ ク 卜ル処理ご と にそれを専門に実行するための回路を用 いる方が望ま し レヽ 。
    [0007] その意味で前述の 、 "内蔵型デー タ ベー スプ ロ セ ッサ は、 ソ ー 卜 の高速処理に適 し て いる 。
    [0008] しか し 、 こ のプ ロ セッサで は 、 ソ ー ト さ れう るべ ク 卜 ルデ ー タ のそれぞれの要素のデー タ 長が、 その計算機に よ り 定め ら れた一定の値でなければ、 ソ ー ト をべ ク 卜 ル 処理に よ り 実行できない 。
    [0009] た と えば 、 前述の " 内蔵型デー タ ベ ー スプ ロ セ ッサ " で は、 ソ ー ト 処理を受け う る ベク ト ルデ ー タ のベ ク ト ル 要素のデー タ 長は 4 パイ 卜 ある い は Ί 2 パイ 卜でなけ れ ばな ら ない 。
    [0010] しかる に 、 ソ ー ト す べきデー タ が地名等の場合 、 上記 一定長よ り 長いデー タ 長を有する場合がある 。 この よ う なデー タ に対 して は 、 前述の " 内蔵型べ ク ト ルプロ セ ッ サ " で は 、 ベ ク ト ル処理でな く ス カ ラ処理に よ り ソ ー ト を実行 して いた 。 このた め処理速度は遅い と い う 問題が あつ た 。
    [0011] したがっ て 、 ベ ク ト ルプ ロ セ ッサに よ り ソ ー ト 可能な デ ー タ 長 と し て定め ら れた デ ー タ 長よ り 長いデ ー タ に 対 し て も ソ ー ト を ベ ク ト ル処理に よ り 実行す る た め の ソ ー 卜 方法お よびそ の方法 に適 し た べ ク 卜 ルプ ロ セ ッサが望 ま れる 。
    [0012] 記号デー タ 列の群 に対 し て べ ク 卜 ル処理を実行す るた めの技術が本譲受人 に譲渡さ れた米国出願 7 3 7 , 6 8 6 ( 1 9 8 5 , 5 ， 2 4 出願 ） に 開示さ れて いる 。 こ の 出願の技術 は 、 記号デー タ 列の群か ら 、 それぞれ一定長 の記号列を要素 と す る べ ク ト ルデー タ を生成 し 、 同一 の 記号デ ー タ 列 に 属す べ き べ ク 卜 ル要素群を部分 べ ク 卜 ル と し て 処理す る 。 こ の際 、 部分 ベ ク ト ルの区切 り を表わ す 今一 つ の ベ ク ト ルデー タ を用 いる 。 こ の技術で は 、 ベ ク 卜 ル処理の例 と して 特定 の記号列 に一致す る記号 列が 記号デ ー タ 列群の 内 に存在す る かを べ ク 卜 ル処理に よ り 検索す る技術が具体的に 示さ れて いる 。 し か し 、 こ の技 術 はソ ー 卜 の方法を開示 し て い な い 。 ま し て 、 前述の よ う に 、 ベ ク ト ルプ ロ セ ッ サ に よ り 定 ま るデ ー タ 長 を こ え るデ ー タ 長を有す る記号列群を べ ク 卜 ル処理に よ り ソ ー 卜 す る方法は開示 し て いない 。
    [0013] 発明の 開示
    [0014] し た がっ て 、 本発明の 目 的は 、 一群のデー タ の内 、 未 ソ 一 卜 の部分をべ ク 卜 ル処理 に よ り 検出 する方法を提供 す る こ と で ある 。
    [0015] ま た 、 本発明の他の 目 的 は 、 そ の よ う な検 出を高速に 実行で き る べ ク 卜 ルプ ロ セ ッ サを提供す る こ と に あ る 。 本発明の他の 目 的は 、 ベ ク ト ルプ ロ セッサに よ り ソ ー 卜 処理の た め に定め たデー タ 長を こ えたデ ー タ 長をそれ ぞれ有する一群のデー タ をべ ク ト ル処理に よ り ソ ー 卜 す る方法を提供する こ と に ある。
    [0016] ま た 、 本発明の他の目 的は、 その よう なソ ー ト 方法を 実施するの に好適なぺ ク トルプ ロ セッサを提供す る こ と を 百的 とする 。
    [0017] 本発明 に よるベ ク ト ルプロ セッサは 、 記憶装置に格納 さ れたべ ク 卜 ルを賬次読み出 し演算するべク ト ル処理装 置に おいて 、 入力 べ ク 卜ル中である特定の条件をみたす 連続するべ ク 卜 ル要素について 、 該連続するべ ク 卜 ル要 素か ら構成さ れる前記入力 べ ク 卜 ルの部分領域の開始 と 終了 を検出する手段 と 、 開始検出時に該部分領域の先頭 ベ ク ト ル要素の位置情報を保存する手段 と 、 終了検出時 に最終ベ ク ト ル要素の位置情報を 、 前記保存さ れた先頭 べ ク 卜ル要素の位置情報と共に 、 前記記憶装置に格納す る手段 と を有する 。
    [0018] ま た本発明 に よるべ ク 卜 ルプ ロ セ ッサは 、 複数のべ ク 十 ル要素か ら なる第 1 のぺ ク トル と 、 各要素が該第 1 の べ ク ト ル内の 1 つ あるい は互いに 隣接する複数のべ ク 卜 ル要素か ら なる部分領域を指定する部分領域指定情報で あ る第 2 のべ ク 卜 ルを記億する装置と 、 該記憶装置から 第 1 、 第 2 の べ ク 卜 ルの要素を頫次読み出す第 1 、 第 2 の読み出 し手段 と 、 第 Ί の読み出 し手段に よ り 頭次読み 出 される べ ク 卜 ル要素に対 し て所定の演算処理を行 う 演 算手段 と 、 該演算手段に よ り 照次生成さ れた演算結果を 前記'記憶装置に頫次書き込みを行 う 手段 と 、 第 2 の読み 出 し手段から読み出さ れた部分領域指定情報か ら 、 第 1 のべ ク 卜 ル内の部分領域に対する読み出 し 開始位置情報 と み出 し終了位置情報 と演算結果の書き込み位置情報 を生成す る部分領域ア ク セ ス情報生成手段 と 、 第 1 の読 み出 し手段につ いて 、 読み出さ れるべ ク 卜 ル要素の位置 .情報を読み出 し に同期 し て 出力 す る部分領域読み出 し位 置情報供給手段 と 、 該部分頜域読み出 し位置情報供給手 段の出力 す る部分領域内のベ ク 卜 ル要素の位置情報 と前 記部分領域ア ク セ ス情報生成手段の 出力 す る読み出 し終 了位置情報 と を 比較 し て 、 部分領域への演算処理の終了 を検出 す る部分領域処理終了判定手段を有 し 、 前記第 2 のべ ク 卜 ルか ら 読み出さ れた べ ク 卜 ル要素を前記部分領 域 ア ク セ ス情報生成手段 に 入力 し 、 出力 さ れた部分頜域 読み出 し 開始位置情報を前記第 1 の読み出 し 手段 に セ ッ 卜 し 、 演算結果書 き込み位置情報を前記書き込み手段に セッ 卜 し た後、 顕次読み出さ れる第 1 のべ ク 卜 ル内の部 分領域のベ ク 卜 ル要素に前記所定の演箅処理を施 し 、 前 記部分領域処理終了判定手段が該部分領域への処理終了 を検出す る毎に 、 第 2 の読み出 し手段を制御す る 。
    [0019] さ ら に 本発明 に よ るソ ー 卜 方法で は 、 各々 が ソ ー 卜 対 象 と なるキ ーデ ー タ 要素を含 む レ コ ー ドデ ー タ 要素を一 定 ま た は不規則な ア ド レス 間隔で保持す るデ ー タ 記憶装 置 と 、 前記キ ー デ ー タ 要素 の有す る要素長に は みた な い 要素長デー タ のソ ー 卜 命令を有す るデー タ 処理装置 に お いて 、 前記各 レ コ ー ドデ ー タ 要素の記憶装置内'での ア ド レス情報か ら なるベ ク ト ルを用 いて 、 各 レコ ー ドデ ー タ 要素につ い て各々 が含む各キー デー タ 要素の先頭か ら前 記ソ ー ト 命令のソ ー ト可能な要素長に相当する長さ のデ ー タ を部分キ ーデー タ と し て読み出 し 、 レコ ー ドデー タ 要素 1 つ につ き 1 つ の割合いで読み出された部分キー デ ー タ の各々 につ い て 該部分 キー デー タ と こ れを含むレコ ー ドデー タ 要素の ア ド レス情報 と を対に して 、 該対デ一 タ の一群を要素デー タ が一定の ア ド レス間隔で配置さ れ るベ ク トルの形式 に従っ て前記記憶装置内 に配列 し 、 該 対デー タ か ら なる ベ ク ト ルを 、 対デー タ の含む部分キー デ ー タ の値に従っ て ソ ー ト し 、 ソ ー ト 結果のべ ク ト ルに つ い て 隣接するべ ク 卜 ル要素で各々 が含む部分キ ー デー タ の値が等 し いもの を未ソ ー ト部分領域と し て検出 し 、 検出さ れた複数の未ソ ー ト 部分領域に対 し て 、 各未ソ ー 卜 部分領域内の未ソ ー 卜 べク 卜 ル要素につ い て 該べ ク 卜 ル要素内の レ コ ー ドデー タ 要素ア ド レス情報をも と に キ 一デー タ ー要素を参照 し 、 該キ ーデー タ 要素内か ら前に 読み出 し た部分キ ー デー タ の直後の部分キーデー タ を読 み出 し て前記未ソ ー 卜 べ ク ト ル要素の部分キ ーデー タ の 値を書き換え 、 全て の未ソ ー 卜 ベ ク ト ル ^素が書き換え ら れた未ソ ー 卜 部分領域について 再びソ ー 卜 及び未ソ ー 卜 部分領域の検出 を繰 り返し適用 し 、 未ソ ー ト 部分領域 の消減をおつ て ソ ー 卜 を完了す る 。 本発明 に よ れば処理対象 と するベ ク ト ル中 に ある 、 特 定 の条件を満す べ ク 卜 ル要素列 、 た と えば互い に同一値 を有す る隣接す る部分要素列を髙速に検出でき る 。
    [0020] ま た 、 本発明 に よ れば、 べ ク 卜 ル中の互い に 瞵接す る 位置に ある一部の要素か ら な る部分べ ク 卜 ルに対 し て べ ク十 ル演算を選択的に行い う る 。
    [0021] ま た 、 本発明 に よ れば 、 ベ ク 卜 ルプ ロ セッサで定 ま る ソ ー 卜 処理可能な一定のデ ー タ 長を こ えるデ ー タ 長か ら な る キ ー 群をべ ク 卜 ル処理 に よ り ソ ー '卜 できる 。
    [0022] 図面の簡単な説明
    [0023] 第 1 図 は本発明 の一実施 ^であ るべ ク 卜 ル処理装置の 構成図 、
    [0024] 第 2 A 図 は第 2 B 図 に 組合さ っ て 、 第 1 図の装置に よ り な さ れる ソ ー 卜 処理の処理フ ロ ー を示 し た 図 、
    [0025] 第 3 A 図 は第 2 Λ 図の処理フ ロ ー の内 、 一つ の圧縮処 理の フ ロ ー を示す 図 、
    [0026] 第 3 B 図 は 、 第 2 A 図の処理 フ ロ ー の内 、 一 つ のマ ル チソ ー 卜 処理の フ ロ ー を示す図 、
    [0027] 第 4 図はマルチソ ー 卜 処理の処理 フ ロ ー を示す 図 、 第 5 A 図 は第 Ί 図 のベ ク 卜 ルプ ロ セッ サに用 いる命令 の形式 とそ れで指定さ れる汎用 レジ ス タ 内のデ ー タ を示 す図 、
    [0028] 第 5 B 図 は 、 第 3 A 図の 圧縮処理お よ び第 3 B 図のマ ルチソ一 卜 処理実行時の 汎用 レ ジ ス タ 内 のデ ー タ 又 は ァ ド レ ス を示す 図 、 第 6 A図 と第 6 B図 は耝み合わさっ て 、 圧縮処理実行 時の タ イ ムチヤ一 卜 、
    [0029] 第 7図はマルチソ ー 卜 処理実行時の タ イ ムチヤ一 卜 、 第 8図は、 第 Ί 図の装置に用いる命令制御回路 1 03 の回路図 、
    [0030] 第 9図は第 Ί 図の装置に用 いる演算制御回路 1 04の 回路の構成図、
    [0031] 第 1 0図は第 1 図の装置に用 いる ア ド レス制御回路 1 1 0の回路図-、
    [0032] 第 Ί Ί Α図 は第 1 図の装置に用 いる圧縮演算回路 1 9 0の回路図、
    [0033] 第 1 1 B図は第 1 1 A図の部分べ ク 卜ル検出論理 " 1 0 4の動作条件を示す図、
    [0034] 第 1 2 A図 は第 1 図の装置に用 いるソ ー 卜 演算回路 1 9 1 の回路図 、
    [0035] 第 Ί 2 B図は、 第 1 2 A図のマ ージ論理 1 2 5 4の動 作条件を示す図、
    [0036] 第 Ί 3図 は第 1 図の装置に用いる部分ベク ト ル処理制 御回路 1 0 5の回路図、
    [0037] 第 1 4図は第 2 A図 と第 2 B図で示さ れたソ ー ト 処理 の.フ ロ ー を示す P A D形式の フ ロ ー チヤ一 卜 図である 。
    [0038] 発明を実施す るための最良の形態 以下、 本発明の実施例 を図面を参照 し て 説明する 。 第 Ί 図 は 、 本発明 によ るベク ト ルプ ロ セ ッサを示す 。 図 において 、 1 0 1 は命令語 レ ジスタ 、 1 0 2は命令解 読回路 、 1 0 3 は解読さ れた命令の実行を制御す る命令 制御回路であ る 。 1 0 4 は 、 ベ ク 卜 ル命令が実行さ れた 場合、 処理済のベ ク ト ル要素数を カ ウ ン 卜 し て 、 必要な 数のべ ク 卜 ル要素が処理さ れた か否かを判定す る演算制 御回路 、 1 0 5 は 、 後述す る 、 本発明 に特徴的な圧縮処 理又はマルチソ ー 卜 処理の た めの 、 部分べ ク 卜 ル処理制 御回路で あ り 、 1 0 9 は汎用 レジ ス タ の群で あ る 。 1 1 0は主記憶装置 1 1 1 か ら読み出 すべ き 2つ の べ ク 卜 ル デ ー タ の 、 そ れぞれの要素の ア ド レスお よ びそ れ ら の二 つ のべ ク 卜 ル要素に 対す る演算の結果得 ら れるベ ク 卜 ル 要素を主記憶装置 1 1 1 に書き込むた めの ア ド レスを発 生 す る ア ド レ ス制御回路で あ る 。 1 1 2 は演算回路で 、 こ の回路 に は 、 ス カ ラ デ ー タ に対 し て 、 通常の ス カ ラ 演 算を行 う ス カ ラ演算回路 1 9 3 、 ベ ク ト ルデ ー タ に対 し て通常の算術又 は論理演算を行う た めのベ ク ト ル演算回 路 1 9 2 、 ベ ク ト ルデ ー タ に 対 し て後述す るマ ルチソ ー 卜 処理を実行す る た めのソ ー ト 演算回路 1 9.1 、 べ ク 卜 ルデ ー タ に対 し て 後述す る圧縮演算を実行す る た めの圧 縮演算回路 1 9 0が含 ま れる 。 こ れ ら の演算回路の内 、 圧縮演算回路 1 9 0は本発明の特徴的な回路で あ り 、 ソ 一 卜 演算回路 1 9 1 は従来公知のマ ー ジソ ー 卜 回路 に実 質的に 類似のマ ー ジソ ー 卜 回路 1 2 5 1 以外に 、 ソ ー 卜 完了判定回路 1 2 5 0を有す る点に特徴が あ る 。
    [0039] 第 2 図 は 、 本発明 に よ るソ ー ト 処理方法.の概略 フ ロ ー チヤ一 卜 で あ る 。 以下、 第 2図 に従っ て 、 本発明の対象 と する任意固定 長キ ー のソ ー ト 処理方法につ いて述べる 。 なお 、 第 1 4 図 は、 このソ ー ト処理フ ロ ーを示す 、 P A D ( Program Analysis Diagram) 形式のフ ロ ー チヤ 一 卜 である 。 第 2 図 φレコ ー ド群 2 0 2は主記憶装置 1 1 1 内に納め られ て いる 。 説明 を簡略化するため 、 レコ ー ド群 2 0 2は等 ア ド レス藺隔でベ ク ト ル と し て主記憶装置 1 1 1 内 に納 め ら れて いるもの とする 。 ま た 、 各 レ コ ー ドの イ ンデッ ク ス （ レコ ー ド番号 ） か らな る レ コ ー ドイ ンデッ ク ス リ ス 卜 2 0 1 が同様に 主記憶装置 1 1 1 内 に格納されて い る 。 各 レ コ ー ド はキー と呼ばれるデ ー タ （ この例で は Ί 2パイ 卜 長と する ） を含んでいる 。 説明を簡単に する た め本実施例では、 レコ ー ド の先頭に キーが納め られて い るもの と す る 。 任意固定長キーのソ ー 卜 処理 と は、 キ ー の大小関係に基き レコ ー ド イ ンデッ ク ス リ ス 卜 2 0 1 を 並べ換える処理を さ す。 よ り 具体的に は 、 本実施例で は キー群を アルフ ァべッ 卜 の頤に指定する よ う に 、 レ コ ー ドイ ンデック ス リ ス 卜 20 1 を並びかえる こ とである 。
    [0040] なお 、 第 1 図のベ ク ト ルプ ロ セッサのソ ー ト 演算回路 1 9 1 は 、 4バイ ト のデー タ に対す る 、 ソ ー ト をべ ク 卜 ル処理に よ り 実行可能である と仮定する 。 以下では、 こ のべ ク トルプ ロ セッサを用いて 、 Ί 2パイ 卜 のキー を含 む レ コ ー ド群 2 0 2のソ ー ト 処理を ベ ク ト ル処理で実行 可能 とす'る方法を示す。
    [0041] 新 し いソ ー ト 処理方法の基本概念は 、 キ ー の先頭に あ る 、 ハ ー ド ウ ェ ア で ソ ー 卜 可 能な長さ （ こ の例で は 4 バ イ ト ） のデ ー タ ソ ー ト を行い 、 そ のソ ー 卜 に よ っ て も依 然 と し て大小関係が確定 し ない レ コ ー ド に つ い て キ ー か ら次の 4 パ イ 卜 デ ー タ を参照 し て ソ ー 卜 を く り 返す こ と に よ り 、 レコ ー ド全体を ソ ー 卜 する と い う も ので あ る 。 ま ず ソ ー 卜 用 の作業領域 と し て 各要素が 8 パ イ 卜 か ら な り 、 レ コ ー ドイ ンデッ ク ス リ ス 卜 2 0 1 と 同 じ要素数を もつ ワ ー ク ベ ク ト ル 2 0 3 用 の エ リ ア を 主記憶装置 1 1 "1 に 用意す る 。 ワ ー ク ベ ク ト ル 2 0 3 の各要素 は 、 4 パ ィ 卜 の フ ィ ー ル ド 2 つ か ら なつ て い る 。 前半 4 ノ ィ 卜 の エ リ ア 2 0 5 を レ コ ー ド イ ンデッ ク ス格納領域 と 呼び 、 後半 4 パ イ 卜 のエ リ ア 2 0 6 を部分キ ー格納領域 と 呼ぶ ま ず 、 レ コ ー ド群 2 0 2 の各 キ ー よ り 、 先頭 4 パ イ 卜 の 第 Ί 部分 キ ー を切 り 出 し 、 ワ ー ク べ ク 卜 ル 2 0 3 の各要 素の後半 4 パイ 卜 に格納す る 。 こ の処理は 、 通常の べ ク 卜 ル計算機 （ 例 え ば 日 立製作所製 " M— 6 8 0 H コ ン ビ ユ ー タ の内蔵ア レ イ プ ロ セ ッサ " ） の有す る リ ス 卜 べ ク 卜 ル命令 （ 前述の例で は V M S X E 〇 命令 ） と第 Ί 図の ベ ク 卜ル演算回路 1 9 2 に よ り べ ク 卜 ル処理 と し て 実現 さ れる 。 次 に 、 レ コ ー ド イ ンデッ ク ス リ ス 卜 2 0 1 の各 要素を ワ ー ク べ ク 卜 ル 2 0 3 の各要素の前半 4 パ イ 卜 に 格納 す る 。 こ の処理に つ い て も通常の ベ ク 卜 ル移動命令 ( 前述 の例で は V M E 命令 ） と 第 Ί 図 の ベ ク ト ル演算回 路 1 9 2 で実行可 能で あ る 。 以上で ワ ー ク べ ク 卜 ル 2 0 3 のデ ー タ がそ ろっ た ので 、 こ れを ソ ー 卜 す る 。 ソ ー ト は第 Ί 図のソ ー ト 演算回路 1 9 1 を甩いて 行う すなわち 、 ワ ー クべ ク 卜 ル 20 3の各要素の後半 4パイ 卜 の値に従ってそれら の要素を並べ換える 。 ソ ー 卜 に際 し て 、 図 に-は示 し て いないも う 1 つ の ワ ー ク べ ク 卜 ルを 用い、 ソ ー ト 桔果はも と の ワ ー ク ベク ト ル 203 と同じ メ モ リ エ リ ア に出力 する こ と とする 。 2 0 4はソ ー ト後 の ワ ー ク ベ ク ト ルを示す 。 ソ ー ト に よ り レコ ー ドの う ち イ ンデッ ク スが 5のもの につ いて は 、 その位置が確定 し たが 、 イ ンデッ ク ス 4 , 2 , 3. 7の レ コ ー ド につ いて は部分キ ー が と も に ' S H I Ν ' であるため レ コ ー ドの 躓序が決定できない 。 ま た イ ンデッ ク ス Ί と 6の レコ 一 ド につ いて も ' Υ 0 Κ 0 ' だけではそれ ら の照序が決定 できない 。 ワ ー ク ベ ク ト ル 2 04の要素の内 、 ソ ー 卜 が 完了 し て いない レ コ ー ド に対する イ ンデッ クスお よび部 分キー の対を要素 と する部分べ ク ト ルを未ソ ー 卜 部分べ ク 卜 ル と い う 。 この例では第 0要素か ら第 4要素か ら な る部分 ベ ク ト ル厶 1 と 、 第 6要素から 第 7要素から なる 部分べ ク 卜ル厶 2が未ソ ー 卜 部分べ ク ト ルである 。
    [0042] ワ ー ク ベ ク トル 2 04よ り 未ソ ー 卜部分 べ ク 卜ル厶 1 厶 2を検出す る処理を次に行う 。 以下、 この処 Sを圧縮 処理 と呼ぶ。 すなわち 、 ワ ー クベク ト ル 20 4の部分べ ク 卜 ル厶 1 、 厶 2のそれぞれの先頭要素の イ ンデッ ク ス T O Pと最終の要素の イ ンデッ ク ス B T Mの対を要素と する ベ ク ト ル （ 以下部分べ ク ト ル指定べク 卜 ル と呼ぶ ） 2 09を出力 する 。 こ の例で は このベ ク ト ル 2 0 9 はそ れぞれ イ ンデッ ク ス対 （ 0 , 4 ) と （ 6 , 7 ) の 2つ の 要素か ら なる 。
    [0043] こ の圧縮処理は 、 第 Ί 図の圧縮演算回路 1 9 0に よ り 実行さ れる 。
    [0044] 部分ベ ク ト ル Δ Ί と 厶 2につ い て はキ ー よ り 残 り の部 分キ ー を参照 し て さ ら に ソ ー ト する必要がある 。 そ こ で 未ソ ー ト 部分べ ク 卜 ル厶 Ί の第 0〜第 4要素の レコ ー ド イ ンデ ク ス を用 いて 、 レ コ ー ド群 2 0 2の内 、 そ れぞれ の要素 に対応す る第 0〜第 4のキ ー の 、 次の 4 バイ 卜 の 部分キ ー を切 り 出 し 、 ワ ー ク ベ ク ト ル 20 4の未ソ ー ト 部分べ ク 卜 ル内の要素の部分キ ー 格納領域に書き込む。 こ の結果、 こ こ の例 で は ワ ー ク べ ク 卜 ル 2 0 4の第 0〜 4要素 に ある ' S H I N ' の値がそ れぞれ ' J U K U ' に 書 き かえ ら れる 。
    [0045] こ の処理 は前述の リ ス 卜 べ ク ト ル命令 と べ ク 卜 ル演算 回路 1 9 2 ( 第 1 図 ） に よ り 実行さ れる 。 未ソ ー ト 部分 べ ク 卜 ル Δ 2 に つ いて も同様 に畫 き換えを行 う 。
    [0046] こ の結果、 ワ ー ク べ ク 卜 ル 2 0 7が得 ら れる 。
    [0047] 次に ワ ー ク べ ク 卜 ル 2 0 7の 2つ の部分ベ ク ト ル Δ Ί 厶 2を再びソ ー 卜 し 、 ソ ー 卜 結果を ワ ー ク べ ク ドル 2 0 7の部分ベ ク ト ル Δ 1 . Δ 2の位置に書き込む。 2 08 はソ ー ト の結果を示す ワ ー ク ベ ク ト ルであ る 。 但 し 、 図 の例で はべ ク ト ル 2 0 7 の要素が すで に アルフ ァ ベ ッ ト 類に なっ て い た ので 、 ベ ク ト ル 2 0 7 と 2 0 8 は同一 と な る 。 こ の よ う に 、 複数の部分ベ ク ト ルのそ れぞれをつ づけて ソ ー 卜 する処理をマルチソ ー 卜 と呼ぷ。
    [0048] このマルチソ ー 卜 は 、 部分 べ ク 卜 ル指定べ ク 卜 ル 2 0 9 を用 いて行なわれる 。 すなわち 、 このべ ク ト ルの第 1 要素を用 いて べク 卜 ル 2 0 7 の部分べ ク 卜 ル厶 1 をソ ー 卜 し 、 引続いて 、 部分ベ ク トル指定ベク トル 2 0 9の第 2要素を用 いて べ ク 卜 ル 2 0 7 の部分べ ク 卜 ル厶 2をソ 一 卜 す る 。 マルチソ ー 卜 は従来のべ ク 卜 ルプロ セッサで は Ί 命令では実行できなかっ たが第 1 図に示すべ ク 卜 ル プ ロ セ ッサは 、 こ れを可能 と す る 。
    [0049] さ て 、 ソ ー ト 結果である ワ ー ク べ ク 卜 ル 2 0 8の内 、 イ ンデッ ク ス値 4 . 2 , 3 . 7 の要素の部分キー はいず れも等 しい 。
    [0050] イ ンデッ ク ス値 Ί , 6の要素につ いて も同 じである 。 前者の イ ンデッ ク ス値を含む部分べ ク 卜 ル Δ 3 お よび後 者の イ ンデッ ク ス値を含む部分ベ ク ト ル厶 4 は未ソ ー ト 部分 べ ク 卜ルであ り こ れ ら を検出す る た め に 、 前述の圧 縮処理を再ぴ行う 。
    [0051] 前回の圧縮処理と異なるもの は、 ベ ク ト ル 2 0 8 の内 部分ベ ク ト ル指定べ ク 卜ル 2 0 9が示す部分ベ ク ト ル厶 1 、 厶 2の各々 につ いて 、 別々 に圧縮処理を実行す る点 である 。 この結果、 部分べ ク 卜 ル厶 Ί か ら は未ソ ー 卜部 分 ベ ク ト ル厶 3が検出さ れ、 同様に部分 ベ ク ト ル厶 2か ら は部分 ベ ク ト ル△ 4 が検出 さ れる 。 さ ら に 、 こ れ ら の 部分べ ク 卜 ルの先頭要素 と最終要素の要素番号を要素 と す る部分べ ク 卜 ル指定べ ク 卜 ル 2 1 0が形成さ れる 。 部 分ベ ク ト ル Δ 1 の う ち 、 第 4要素 （ 5 , S E N A ) は 、 他の第 0〜 3要素 よ り 大きいので 、 未ソ ー ト 部分 べ ク 卜 ル厶 3 に は含 ま れない こ と に なる 。 部分べ ク 卜 ル指定べ ク 卜 ル 2 0 9内の要素の値 と ワ ー ク べ ク 卜 ル 2 0 8 内の 要素 と 、 部分ベ ク ト ル指定ベ ク ト ル 2 1 0の各要素の値 と の関係を第 3 A図 に示す 。 複数の部分べ ク 卜 ルを—括 し圧縮処理す る こ と を従来のべ ク 卜 ル処理装置で はべ ク 卜 ル処理 と し て実行す る こ と ができ な かっ た 。 第 1 図の べ ク 卜 ルプ ロ セ ッサで は こ の処理を 1 命令で実行可 能に す る 。
    [0052] こ の圧縮処理後 、 ベ ク 卜 ル 2 0 8の部分べ ク 卜 ル厶 3 と Δ 4 に 含 ま れるべ ク 卜 ル要素の畫き換えがな さ れる 。 す なわち レコ ー ド群 2 0 2 す なわち 、 部分 ベ ク ト ル Δ 3 につ い て は次の処理がな さ れる 。 部分ベ ク ト ル指定べ ク ト ル 2 1 0の最初の要素が示す ベ ク ト ル 2 0 8内の第 0 〜第 3要素に 含 ま れる レ コ ー ド イ ンデッ ク ス値 4 . 2 , 3 , 7 を読み出 し 、 こ れ ら の イ ンデッ ク ス値の レ コ ー ド の第 3部分キ ー を レ コ ー ド群 2 0 2 よ り 読み出 し 、 べ ク ドル 2 0 8の第 0〜第 3要素の部分キ ー格钠頜域に 書き 込む。 部分べ ク 卜ル厶 4 に つ い て も同様であ る 。
    [0053] こ の処理は従来のべ ク 卜 ル処理装置に 用意さ れる リ ス 卜 ベ ク ト ル命令を部分 ベ ク ト ル厶 3 、 Δ 4毎に繰 り 返す こ とで実行可能で あ る 。 第 2 B図 に お いて 、 2 1 1 は こ の結果得 ら れるベ ク 卜 ルを示す 。 部分 べ ク 卜 ル指定 べ ク 卜 ル 2 1 0を利用 し て ワ ー ク ベ ク ト ル 2 1 1 の部分 べ ク ト ル Δ 3 、 厶 4 に対 して 、 前述のマルチソ ー ト を行う 。 2 1 2がマルチソ ー 卜 の桔果得 られた ワ ー ク べ ク 卜 ルで ある 。 第 3 Β 図 は、 こ のマルチソ ー 卜 処理に関与するべ ク 卜 ルを示す 。 未ソ ー ト 部分領域厶 3 と 厶 4 に含ま れる 部分キ ー がすべて異なるか ら 、 レコ ー ドの頭序関係が確 定 し 、 ソ ー ト が終了 したこ とがわかる 。 この よ う に 、 未 ソ ー 卜部分ベ ク ト ルがな く なるかま た は切 り 出すべき部 分キー がな く なっ た 時点でソ ー 卜 は終了する 。
    [0054] ワ ー ク ぺ ク 卜 ル 2 1 2 内の レ コ ー ド イ ンデ ク ス列が レ コ ー ド群 2 0 2 ( 第 2 Α図 ） に対するソ ー ト 結果を示す これを周知のぺ ク 卜ル移動命令によ り 、 レコ ー ドイ ンデ ッ ク スリ ス 卜 2 0 1 ( 第 2 A 図 ） に格納す る こ とでソ ー 卜 が終了する 。
    [0055] 以上説明 した方法に よ り 、 ソ ー ト 処理可能なデー タ 長 に 限 り があるベ ク ト ルプ ロ セッサで 、 任意固定長のキー を含む レ コ ー ドのソ ー 卜 が実現可能 となる 。
    [0056] 本ソ ー 卜 処理方法の特長は以下の 2 点である。
    [0057] (1) ベ ク ト ル化率が高 く 、 加速率が大きい 。
    [0058] (2) 部分キー のソ ー ト によ り 大小関係が確定 し た レコ ー ド につ いて は、 残り の部分キ ー を参照 しないので効率的 である 。
    [0059] 本実施例て" は簡単の ため主記憶装置上で の レコ ー ド の 間隔を等し いもの と し 、 ま た レ コ ー ド先頭に キ ー が含ま れる と し たが 、 レコ ー ドが任意の間隔であっ て も 、 ま た レコ ー ド先頭か ら キー が始 ま っ て いな く て も よ い こ と は 1 明 ら かで あ る 。 ま た キ ー の長さ もソ ー 卜 可能なデ ー タ 長 の整数倍でな く て も支 し つ かえ ない （ 半端な長さ と なつ た 部分キ ー に対 し て はべ ク 卜 ルシ フ 卜 命令を用 いればよ い ） こ と も明 ら かであ る。
    [0060] 次に 、 第 1 図のベ ク ト ルプ ロ セ ッサの動作につ いて 詳 細説明を行う 。 前述の よ う に 、 本発明 に よ るソ ー 卜 処理 方法 は通常の ベ ク 卜 ル命令 （ 移動命令 、 リ ス 卜 べ ク 卜 ル 命令 、 シ フ ト 命令な ど ） と圧縮処理を行 う 命令 、 マルチ ソ ー 卜 処理を行 う 命令を組み合わせ て 用 い る こ と に よ り 実行さ れる 。
    [0061] 第 Ί 図 に お いて 、 主記憶装置 1 1 1 に はソ ー ト 対象の レ コ ー ド群 2 0 2 ( 第 2 A 図 ） 及びソ ー ト 用 プ ロ グラ ム ( 図示せず ） が収め られて いる 。 主記憶装置 1 1 1 よ り 読み出さ れた命令 は命令語 レ ジ ス タ 1 0 1 に 格納 さ れ、 解読回路 1 0 2 で命令がデコ ー ド さ れる と 、 命令制御回 路 1 0 3 がその命令実行の た め の制御信号を他のい ろい ろ の 回路 に送出 す る 。 命令で指定さ れた 、 ベ ク ト ル処理 の た め に 主記憶装置 1 1 1 か ら 読み出す べきべ ク 卜 ルお よび上記べ ク 卜 ル処理の桔果 と して 主記憶装置 1 1 1 に 書き込むべ きべ ク ト ルの ア ド レス情報 は汎用 レ ジ ス タ 群 0 9 よ り ア ド レ ス制御回路 1 1 0 に送 ら れる 。 ァ ド レ ス制御回路 1 1 0 は こ の ア ド レ ス情報 に 基づき 、 読み出 す べ きべ ク 卜 ルある い は書込むべき べ ク ト ルの要素の ァ ド レ ス を照次発生 し 、 そ れ ら を主記憶装置 1 1 1 に 与え る 。 演算回路 1 1 2内の 、 通常のベ ク ト ル演算のた めのベ ク 卜 ル演算回路 1 9 2 、 圧縮演算回路 1 9 0、 マルチソ 一 卜 を行う ソ ー 卜 演算回路 1 9 1 は命令制御回路 1 03 に よ り 、 命令の種類に従っ て選択的に起動される。
    [0062] 笋算結果は主記憶装置 1 1 1 に躓次格钠される 。 演算 制御回路 1 0 4は、 ベク トル処理に おける実行済要素数 の カ ウ ン ト を行い 、 すべて の要素について処理がなされ る と 、 命令終了信号を命令制御回路 1 0 3 に送出する 。 以上の過程を操り 返すこ と に よ り 、 プ ロ グラ ムが実行さ れる。 なお 、 ス カ ラ演算回路 1 9 3 はス カ ラ処理用 の命 令の実行のため に命令制御回路 1 0 3 に よ り 起動さ れる まず、 第 3 A図 に示すベ ク ト ル 2 0 8 , 2 0 9を例 に 用 いて 、 圧縮処理を実行する ときの第 1 図の装置の動作 の概略を説明する 。
    [0063] 以下、 圧縮処理の説明に おいて 、 部分ベ ク ト ル指定べ ク 卜 ル 2 0 9 、 ワ ー ク べ ク 卜 ル 2 0 8 、 部分べ ク 卜 ル指 定ベ ク トル 2 1 0をそれぞれベ ク ト ル X , Υ , Z と呼ぶ 第 5図 に示す よ う に 、 本実施例で用いる圧縮命令又は マルチソ ー ト 命令は、 命令の種類を示す O Pコ ー ド と 、 2つ の汎用 レ ジスタ 番号 R 1 . R 2を含む。 汎用 レジス タ 群 1 0 9 は、 簡単化のた め に図示していない レジス タ を含めて 1 6本の汎用 レ ジス タ か ら な り 、 命令の 、 番号 R 1 、 R 2 に応答 し て番号 R 1 . R 2 , R 2 + 1 R 2 + 2の汎用 レ ジ ス タ （ 以下 G P R ( 1 ) 、 G P
    [0064] ( R 2 ) 、 G P R ( R 2 + 2 ) 、 G P R ( R 2 + 2 ) と 呼ぶ ） の内容を出力 する 。
    [0065] 汎用 レジ ス タ G P R ( R 1 ) に は第 2オ ペラ ン ド
    [0066] ( 0 P . 2 ) と し て使用 す るベ ク ト ルの要素数、 汎用 レ ジ ス タ G P R ( R 2 ) は第 2オペラ ン ドベ ク ト ルの先頭 要素の ア ド レス 、 汎用 レジス タ G P R ( R 2 + 1 ) に は 第 3オ ペラ ン ド と して用 いるべ ク 卜 ルの先頭要素の ア ド レス 、 汎用 レ ジス タ G P R ( R 2 + 2 ) に は 、 第 Ί オ ペ ラ ン ド と し て用 いるベ ク ト ルの先頭要素の ア ド レ ス を あ ら か じ め セ ッ 卜 し て お く 。
    [0067] 第 3 A図の圧縮処理を起動する圧縮命令を実行 す る場 合 に は 、 ベ ク 卜 ル X , Υ , Zがそれぞれ第 2 , 第 3 、 第 1 オ ペ ラ ン ド と し て 使用 さ れ る 。 し た が っ て 、 こ の 命 令の実行前 に 汎用 レ ジ ス タ G P R ( R 1 ) 、 G P R
    [0068] ( R 2 ) 、 G P R ( R 2 + ) 、 G P R ( R 2 + 2 ) の 汎用 レ ジ ス タ に は第 5 B図の圧縮命令の攔に示 し た デ ー タ 又 は ア ド レ ス をあ ら か じ め セ ッ 卜 し て お く 。
    [0069] 圧縮命令 が命令語 レ ジ ス タ 1 0 1 に セ ッ ト さ れ 、 解読 回路 1 0 2に よ り 解読さ れる と 、 命令制御回路 1 0 3は 汎用 レジ ス タ 群 1 0 9 よ り べ ク 卜 ル Xの要素数 （ こ の場 合 は 2 ) を演算制御回路 1 0 4に セ ッ ト し 、 ベ ク ト ル X Υ , Zの先頭要素の ア ド レ スを ア ド レス制御回路 1 1 0 に 送出する 。 ア ド レス制御回路 1 1 0に よ り ま ず べ ク 卜 ル Xの第 0要素 （ 0 , 4 ) が主記憶装置 1 1 1 に よ り 読 み出さ れ 、 部分 べ ク 卜 ル処理制御回路 1 0 5に 送 ら れる , 部分ベ ク ト ル処理制御回路 1 0 5内 の要素イ ンデ ク ス生 成回路 1 8 2は、 入力さ れたべ ク 卜 ル Xの第 0要素の内 ， べ ク 卜 ル Y内の部分べ ク 卜ル厶 1 の先頭要素の イ ンデ ク ス T O P ( この場合は ' 0 ' ) を取 り 出 し て これをア ド レス制御回路 1 1 0と 、 演算制御回路 1 04に送出する , ま た部分べク 卜 ル厶 1 の最終要素のィ ンデク ス B T M
    [0070] ( この場合は ' 3 ' ) を取り 出 して これを圧縮演算回路 1 9 0に送出する 。 ア ド レス制御回路 1 1 0は受け とつ た 厶 1 の先頭要素へのイ ンデクス T O Pと 、 ベ ク トル Y の先頭要素のア ド レス とか ら 、 部分ベ ク ト ル厶 1 の要素 の ア ド レス を頫次主記憶装置 1 1 に送出 し 、 それに同 期 し て命令制御回路 1 03はフ ェッ チ要求信号を主記憶 装置 1 1 1 に送出 し 、 それ ら の要素の読出 し を指示する べ ク 卜 ル Yの部分べ ク 卜 ル厶 Ί の読み出 し が開始さ れる と 、 命令制御回路 1 03は、 ベ ク ト ル Xの次の要素の読 み出 しを 、 部分べ ク 卜 ル厶 1 に対す る以下の処理が終了 する ま で、 停止する 。 主記憶装置 1 1 1 よ り ） 次フ ェツ チさ れた部分 べ グ 卜 ル Δ Ί の要素は演算回路 1 1 2内の 圧縮演算回路 1 9 0に送出さ れる 。 圧縮演算回路 1 9 0 で は、 部分ベク ト ル判定回路が順次受け とつ た ベ ク ト ル 要素の隣り合う もの同志を比較する 。 両者が一致する と 例えば部分べ ク 卜ル厶 1 の第 " 1 要素が読み出さ れ、 それ が第 0要素 と一致する こ と が検出さ れた とき 、 部分べ ク 卜 ル判定回路 1 1 5 0は未ソ ー ト 部分べ ク 卜 ル （ 今の場 合は 厶 3 ) の検出開始 と判断する 。
    [0071] 以下、 異なる値の要素が読み出さ れる ま で 、 本例では 第 4要素が読み出さ れる ま で 、 圧縮演算回路 1 9 0は特 に 何も し ない 。 第 4要素の ' S E N A ' は第 3要素の ' J U K U ' と異なるので こ の第 4要素が読み出さ れた と き に 、 部分 べ ク 卜 ル判 定 回 路 1 1 5 0 は 未 ソ ー 卜 部 分ベ ク ト ル （ - 厶 3 ) の検出終了 と判断 し 、 すで に検出 し た部分べ ク 卜 ル厶 3の先頭要素の イ ンデッ ク ス値 と ' 0 ' と 、 演算制御回路 1 0 4が出力 す る現在の要素の イ ンデッ ク ス値 （ 今の場合 は ' 4 ' ) の 1 つ 前の イ ンデ ッ ク ス値で ある ' 3 ' と の対 （ 0 , 3 ) を主記憶装置 1 1 1 に送 り 、 ベ ク ト ル Zの第 1 要素 と し て 格納 す る 。 一方、 演算制御回路 1 04は 、 圧縮演算回路 1 9 0で べ ク 卜 ルの一 つ の要素が処理さ れる毎 に実行中 のべ ク 卜 ル要素の イ ンデッ ク ス値を 1 ずつ 増や す 。 そ の イ ンデッ ク ス値は部分べ ク 卜 ル処理制御 回路 1 0 5内の部分終了 判定回路 1 8 0に逐次報告さ れる 。 部分べ ク 卜 ル Δ 1 内 の第 4要素が処理さ れ、 ベ ク ト ル Yの実行中要素の イ ン デッ ク ス値が ' 5 ' に な る と 、 Δ 1 の最終要素の イ ンデ ッ ク ス値 B T M ( = 4 ) を こ えた こ と に なる ので部分終 了判定回路 1 8 0は部分べ ク 卜 ル厶 1 の処理終了 を検出 し 、 部分処理信号を完全終了判定回路 1 8 1 に送出す る こ の信号 に 応答 し て 完全終了判定回路 1 8 1 は解読さ れ た 命令が圧縮命令の場合 は 、 特別 な処理を施さ ず に 完全 処理終了 信号を命令制御 回路 1 0 3 に送出す る 。 部分べ ク 卜 ル厶 1 の処理終了信 -号を受け と つ た 命令制御回路 " 1 0 3 は 、 抑止 し て い た べ ク 卜 ル Xの次の要素 に対する フ エッ チ要求信号を出力 し 、 主記憶装置 1 1 1 から べ ク 卜 ル Yの次の部分ベ ク ト ル厶 2を指定する 、 ベ ク ト ル Xの 次の要素 （ 6 , 7 ) を読み出す 。 以下、 部分ベク トル厶 2 に対 して も同様な処理が進行 し 、 ベ ク 卜ル Xの要素が 尽きる と 、 圧縮命令の実行が終了 す る。
    [0072] 本ベ ク ト ルプ ロセッサで は 、 上述の よ う にベ ク ト ル Y の部分べ ク ト ルの処理が終了 する毎にぺ ク ト ル Yの次の 部分ベ ク ト ルを指定する 、 ベ ク ト ル Xの次の要素が フ エ ツ チさ れる ので、 複数の部分ベ ク ト ル厶 1 、 Δ 2をつ づ けて処理する こ とが可能 となる 。 従って個々 の部分べク 卜 ル毎に ベ ク ト ル処理を行う 場合 と比べて 、 長いべ ク 卜 ル長を確保できる と い う利点がある 。
    [0073] 次 にマルチソ ー 卜 処理命令の実行時における第 Ί 図の ベ ク ト ルプ ロ セ ッサの動作概略を、 第 3 Β図 に示すべ ク 卜 ルデー タ を例 に用 いて述べ る 。
    [0074] 以下の 、 マルチソ ー ト 処理の概咯説明で は、 部分べ ク 卜 ル指定 べ ク 卜 ル 2 1 0、 ソ ー 卜 す べきベ ク トル 2 1 1 をベ ク ト ル Ζ , Υと呼ぷ。 以下の処理で は、 第 Ί 図に示 す よ う に主記憶装置 1 1 1 内の作業用領域 と し て 、 べ ク ト ル Υ と 同型の べ ク ト ル Wの 領域も 用 い る 。 マル チソ 一 卜 で はべ ク 卜 ル Ζの先頭要素が示す先頭要素番号 T O P ( = 0 ) と最終要素番号 B T M ( = 4 ) で指定さ れる 、 ベ ク ト ル Yの最初の部分べ ク 卜 ル （ 厶 3 ) のソ ー 卜 を実行 し 、 その後、 ベ ク ト ル Zの次の要素にて指定さ れる 、 ベ ク ト ル Yの部分べ ク 卜 ル （ 厶 4 ) をソ ー 卜 する 各部分べ ク 卜 ルのソ 一 卜 の た め に 、 要素イ ンデッ ク ス 生成回路 1 8 2 と ア ド レ ス制御回路 1 1 0は 、 各部分 べ ク 卜 ル （ た と えば厶 3 ) 内のソ ー ト す べきベ ク ト ル要素 を 、 ベ ク ト ル Zの要素に 応答 し て フ ェッチす る 。
    [0075] 第 4図 は 、 第 3 B図のマルチソ ー 卜 処理の実行の手頫 を詳 し く 示 し た 図である 。 こ のソ ー ト方法で は 、 ソ ー ト す べ きべ ク 卜 ル （ 今の例で は部分べ ク 卜 ル厶 3 ) を さ ら に 2つ の部分ベ ク ト ルに分け 、 そ れ ら をソ ー ト 処理 4 0 1 に よ り ソ ー 卜 し て ベ ク ト ル Wを得 、 次 に ベ ク ト ル Wに 対 し て同 じ よ う な ソ ー 卜 処理 4 0 2を行 う 。 ベ ク ト ル Δ 3のソ 一 卜 終了後、 ベ ク ト ル厶 4 に つ い て も周様の処理 4 0 3 、 4 0 4を実行 す る 。 こ の図で 、 F . Sはそれぞ れソ ー 卜 す べき べ ク 卜 ルの読み出 し お よびソ ー 卜 結果の ベ ク ト ルの書き込みを示す 。 ま た 、 矢印 は読み出 し お よ び書き込みさ れる ベ ク ト ル要素の範囲 を示す 。 マ ー ジ ソ 一 卜 処理 4 0 1 〜 4 0 4自体お よ びそ れ ら を橾 り 返 し て —つ の ベ ク ト ルを ソ ー 卜 す る こ と 、 お よびそ の際べ ク 卜 ル Yと Wを交互に ソ ー 卜 対象 、 ソ ー 卜 結果格納べ ク 卜 ル と し て 用 いる点は 、 本讓受人 に譲渡さ れた米国特許出願 S N 6 8 5 , 1 Ί 6 ( Ί 9 8 4年 1 2月 2 1 日 出願 ） に 示 し た の と 同様で あ る 。 し か し 、 上記公知技術で はマ ー ジ ソ ー 卜 処理 4 0 1 等の橾 り 返 し 回数が 、 ソ ー 卜 完了 か 否か に 関係な く ソ ー 卜 す べき デー タ の数 に依存 し て 定 ま る一定 回数に 定 ま っ て い た が 、 本実施例で は 、 ソ ー 卜 未 完了 の 間 は 、 上記マ ー ジ ソ ー 卜 処理 4 0 1 等を繰 り 返 し ソ ー 卜 完了時に操り 返 し を止める。
    [0076] 第 4図の例で はマージソ ー ト 処理 40 1 はべ ク 卜 ル Y をソ ー 卜対象ベ ク ト ル と し 、 ベ ク ト ル Wをソ ー 卜桔果格 納用 べ ク 卜ル と している が、 マ ージソ ー 卜処理 40 2で はべク 卜ル Wをソ ー 卜対象ベ ク ト ル と し 、 ベ ク ト ル Yを ソ ー ト 結果格納用 べ ク 卜ル となっ て いる 。 この場合、 上 記 1 回の逆転使用でソ ー 卜 が終了 して いる 。
    [0077] 本実施例では一般に はマ ー ジソ ー ト処理 40 1 , 40 2等を 、 部分ベ ク ト ル Δ 3のソ ー ト が終了す るまで继铳 す る所に特徴がある 。 このた め、 本実施例で は 、 次の 2 つ の回路を採用 した 。
    [0078] まず第 Ί 図 に 、 部分べ ク个 ルのマ ージソ ー ト 処理 40 1 等を 1 回終了する毎に ソ 一 卜 が完了 し たか否かを判定 するソ ー ト 完了判定回路 Ί 2 5 0をソ ー ト 演算回路 1 9 7内 に設けた 。
    [0079] 第 2の特徴的回路である完全終了判定回路 1 8 1 は部 分終了判定回路 1 8 0か ら の 、 一 回のマ ー ジソ ー 卜処理 ( た と えば処理 40 1 又は 40 2など ） の終了 を示す部 分終了信号 とソ ー 卜 済であるか否かを示す上記判定信号 と の論理積を とるこ と に よ り 、 次の部分ベ ク トルの フ エ ツ チに移るか、 周 じ部分べク 卜 ルに つ いて再度マ ー ジソ 一 卜 処理を接り返すか否かを判定する 。
    [0080] 同一の部分べク ト ルに対 し てマ ー ジソ ー 卜 処理を繰り 返す場合に は、 ソ ー ト 対象ベ ク ト ル とソ ー ト 結果格納用 のべ ク ト ルの交換をア ド レス制御 回路 1 1 0内で フ ェツ チア ド レス と べ ク 卜 ルス 卜 ァ ア ド レ スを切 り 換える こ と に よ り 実現す る 。 第 4 図の例で言えば 、 部分べ ク 卜 ル Z の先頭要素の イ ンデッ ク ス値は " 0 " と " 3 " である の で 、 ベ ク ト ル Y の第 0 要素〜第 3 要素の 4 要素が ま ずソ — 卜 対象 と して フ ェッチさ れる 。
    [0081] 一方 、 結果格納用 のベ ク ト ル Wに はその先頭要素か ら 結果が格钠さ れる 。 こ の 目 的のた め に 、 要素イ ンデ ク ス 生成回路 1 8 2 は べ ク 卜 ル Z の先頭要素の イ ンデッ ク ス 値 " 0 " 、 " 3 " を ア ド レス制御回路 1 1 0 に 送出す る ア ド レ ス制御回路 1 1 0 内の部分ベ ク ト ルア ド レス生成 回路 1 0 5 1 で は こ れ ら の 3 つ の イ ンデク ス値に 従っ て フ ェッ チ先頭 ア ド レ ス と し て べ ク 卜 ル Y の第 0 、 第 2 要 素の ァ ド レ ス と ベ ク ト ル Wの第 0 , 第 2 要素の ア ド レ ス ス ト ア先頭ア ド レス と し て ベ ク ト ル Y の第 0 要素の ア ド レス と ベ ク ト ル Wの第 0 要素の ア ド レスを生成す る 。 生 成 し た ア ド レ ス は部分ベ ク ト ル ア ド レス生成回路 1 0 5 1 内 に保持さ れる と と も に メ モ リ ア ド レス 回路群 1 0 5 0 に送 ら れる 。 こ れ ら の ア ド レスを用 い て 、 ア ド レ ス制 御回路 1 1 0 内の メ モ リ ア ド レ ス回路群 1 0 5 0 に よ り ベ ク ト ル γ の第 0 要素か ら始 ま る部分べ ク 卜 ルお よびべ ク 卜 ル Y の第 2 べ ク 卜 ル要素か ら始ま る部分べ ク 卜 ルを ソ ー ト 対象ベ ク ト ル と し て 主記憶装置 1 1 1 よ り 読み出 し 、 そ れ ら に対す るソ ー ト 結果をベ ク ト ル Wの先頭要素 位置か ら 類 に 書き込む。 こ う し て マ ー ジ ソ ー 卜 処理 4 0 1 がな さ れ 、 それが終了 し た 時点で 、 前述の部分終了判 定回路 1 8 0 か ら部分べク 卜 ル厶 3 の部分終了信号が送 出される 。 第 3 B 図の例では 、 こ の とき、 完全終了判定 回路 1 8 1 からソ ー ト が完全になされて いない旨の信号 がなされる。 メ モ リ ア ド レス回路群 1 0 5 0 は 、 フ ェツ チすべきぺク 卜 ルの ア ド レス と し て ベ ク ト ル Wの第 0， 2 要素の ア ド レスを決定 し 、 ベ ク ト ル Wの第 0要素か ら 始 ま る部分ぺ ク ト ル とぺク 卜ル Wの第 2 要素か ら始ま る 部分ベ ク ト ルを フ ェッチする 。 ス ト ア先頭ア ド レス と し てベク ト ル Y の第 0 要素の ア ド レスを決定 し 、 ベ ク ト ル Wの上記 2 つ の部分べ ク 卜ルに対するマー ジソ ー ト 処理 4 0 2 の結果ベ ク ト ルを、 べ ク ト ル Y の第 0要素〜第 4 要素位置に格納する 。
    [0082] マ ー ジソ ー ト 処理 4 0 2 の終了後は、 ベ ク ト ル Y の部 分べ ク 卜ル厶 3 は完全にソ ー 卜 済み と なるので 、 完全終 了判定回路 1 8 1 は部分ベ ク ト ル厶 3 のソ ー ト 処理が完 全に終了 し た旨の信号を命令制御回路 1 0 3 に送出 し 、 ア ド レス制御回路 1 1 0 は命令制御回路 1 0 3 から の信 号に応答 し て次の部分ベ ク ト ル厶 4 の次の要素 （ 6 , 7 ) をベ ク ト ル Z よ り フ ェッ チする 。 以下周様 に してべ ク 卜 ル Yの部分ベ ク トル厶 4 に対 し てソ ー ト が実行される 。
    [0083] 上記の よ う に本発明で は部分べ ク ドル厶 3 、 厶 4 を一 括 し てつづけてベ ク ト ル処理する こ とが可能 となる 。 従 来のベ ク ト ルプ ロセ ッサ （ 例えば 日 立製作所製〃 M 6 8 0 H 内蔵デー タ ベ ー スプ ロ セッサ " ） で は部分ベク ト ル 毎にソ ー ト 命令を行う 必要がある （ 第 4 図の例でい う と 、 M 6 8 0 H内蔵デ ー タ ベ ー スプ ロ セ ッ サで は M S O R T 命令を 4回発行す る必要が あ る ） 。 従っ て 部分べ ク 卜 ル の要素数が少い と べ ク 卜 ル命令の起動 オ ーバ ヘ ッ ド が大 きい とい う 問題が生 じ る が本発明で は こ の心配がな い 。
    [0084] 次に 、 第 3 A図 に挙げた べ ク 卜 ル X , Υ , Zを例 に と り 圧縮命令の実行時の 、 第 1 図の装置の動作を詳細 に説 明 す る 。 以下に お いて 、 図面に 示さ れた 、 信号線 に 付さ れた 参照番号 は と く に 引用 し な いが同 じ 参照番号 は同 じ 信号線を示す 。
    [0085] 第 6 A図 、 第 6 B図 は 、 第 3 A図の圧縮処理を実行 す る と きの第 1 図の べ ク 卜 ルプ ロ セ ッサの動作を示す タ イ ム チ ャ ー ト で あ る 。 本ベ ク ト ルプ ロ セ ッサで は ク ロ ッ ク K 0 及び ！ を 基本マ シ ー ン ク ロ ッ ク 信号 と し て 用 い て い る 。 第 6 B図 の 内 、 そ の 上 部 に 示 し た " 才 ー ゾ ラ ッ プ " 期間 の部分 は第 6 A図 の一 部分 と オ ー バ ラ ップ し て 示 し て ある 。 さ て 、 命令語 レ ジ ス タ 1 0 1 に 読み出 さ れ た 第 5図の形式 の ベ ク ト ル命令の解読の結果 、 圧縮命令 又 はマルチソ ー ト 命令で ある こ と が判明 す る と 、 そ の旨 を示す信号 D E Cと圧縮命令かマルチソ ー 卜 命令 かを示 す信号 I N S Tが 、 命令制御回路 1 0 3 に 送 ら れる 。 圧 縮命令の場合 、 I N S Tの値 は " 0 " で あ り 、 マルチソ 一 卜 命令 の場合 、 信号 1 N S Tの値は " 1 " と す る 。
    [0086] 命令制御回路 1 0 3の内 、 圧縮命令お よ びマ ル チソ ー 卜 命令の実行 に 関与 す る部分 の構成を第 8図 に 示す 。 こ の 回路 は 、 初期化信号 I N I Tお よ び ク ロ ッ ク 信号 、 K 3 00 , Κ 3 1 0. Κ 3 0 1 , Κ 3 Ί 1 、 Κ 3 0 2 、 Κ 3 1 2を出力 する ク ロ ッ ク発生回路 Ί 03 Αと 、 主記 億装置 1 1 1 へ供給す べきベ ク ト ル要素フ ェッ チ要求信 号 F T 2、 F T 3 P , F T 3 S , ベ ク ト ル要素ス ト ア要 求信号 S Tを発生する要求発生回路 1 03 Bよ り なる 。 図に おいて F Fはフ リ ップフ ロ ップを示す 。 他の図 に お いても同様である 。
    [0087] フ ェッ チま た はス 卜 ァ動作の基本 となる基本信号 F T Q は初期化信号 I N I Tの Ί . 5 ク ロ ッ ク 後に 立上 が り 、 以後 3 ク ロ ッ ク毎に Ί ク ロ ッ ク の間 " 1 " と なる フ ェッ チ要求信号 F T 2 , F T 3 .
    [0088] F T 3 S とス ト ア要求信号 S Tは基本信号 F T Q を必要 に応じ てマ ス ク す る こ とで生成さ れる 。 但 し 、 フ ェッ チ 要求信号 F T 3 Sは圧縮命令実行時 に は甩い ら れない 。 ま た、 初期化信号 I N I Tと ク ロ ッ ク K Q の 立ち 上が り と同期 し て 、 3 ク ロ ッ ク周期 の信号 K 3 0 0、 以下 0. 5 ク ロ ッ ク すつ ずれる形で K 3 1 0 , K 3 0 , K 3 1 1 , K 3 0 2. Κ 3 Ί 2の 6信号が何れも 3ク ロ ッ ク 周期で発生さ れ、 各回路 に供給さ れる 。
    [0089] 第 1 0図 はア ド レス制御回路 1 1 0の構成を示す 。 ァ ド レス制御回路 1 1 0は、 第 2オペラ ン ド と して使用 さ れるべ ク 卜ルを フ ェッ チするため に 、 その要素の ァ ド レ ス を生成する O P . 2フ ェッ チア ド レス回路 1 0 9 9 と 第 3オペ ラ ン ド と し て 使用 さ れるぺ ク ト ルを フ ェッ チす る た め に 、 そ の要素の ア ド レスを生成す る 、 O P . 3第 1 フ ェッ チア ド レ ス回路 1 0 9 8 、 O P . 3第 2フ ェツ チア ド レ ス回路 1 09 9 、 お よびベ ク ト ル処理の結果得 ら れる 、 第 Ί オペラ ン ド と し て使用 さ れるベ ク ト ルをス 卜 ァ す るた め に 、 そ の要素の ア ド レ スを生成す る O P . 1 ス 卜 ァ ア ド レス回路 1 09 6か ら なる メ モ リ ア ド レス 回路詳 1 05 0を有する 。
    [0090] 0 P . 2 フ ェッ チア ド レス回路 1 09 9 は 、 汎用 レ ジ ス タ G P R ( R 2 ) か ら与え ら れる先頭要素 ア ド レス に 基づい て 後続の要素の ア ド レ ス を頭次生成す る が 、 他の ア ド レ ス回路 1 09 6〜 1 0 9 8 は 、 部分ベ ク ト ル先頭 ア ド レ ス生成回路 1 0 5 1 か ら与え ら れる先頭要素 ア ド レ ス に基づいて 後続のべ ク 卜 ル要素の ア ド レ ス を生成す る 。 1 0 9 5は こ の回路 1 0 5 1 で 、 生成 し た ア ド レ ス を ア ド レス回路 1 09 6〜 1 0 9 8 に適宜与 え る た めの ア ド レ ス 切換え回路である 。 さ て 、 第 3 A図 に示 し た圧 縮処理の と き に は 、 O P . 2 フ ェ ッ チア ド レ ス 回路 1 0 9 9で は 、 汎用 レ ジス タ G P R ( R 2 ) か ら 与え ら れる ベ ク ト ル Xの先頭要素がセ ッ ト さ れる レジ ス タ 1 0 0 1 の内容を 、 その後 に完全終了判定回路 1 8 か ら 完全終 了信号 P V F E N Dが供給さ れるたびに 、 + 8加算器 3 0 0 1 で + 8 し て セ レ ク タ S E Lを介 し て レ ジ ス タ 1 0 0 1 に セッ 卜 す る 。 こ う し て 、 ベ ク ト ル Xの先頭要素か ら順 に 、 そ の要素の ア ド レス を発生 す る 。 部分 べ ク 卜 ル 先頭ア ド レ ス生成回路 1 0 5 1 は 、 O P . 2 フ ェ ツ チア ド レ ス 回路 1 0 9 9の働き に よ り 主記憶装置か ら読み出 さ れたベ ク ト ル Xの要素に て指定さ れる 、 ベ ク ト ル Yの 部分ベ ク ト ル （ た と えぱ厶 1 ) の先頭要素の ア ド レスを 算出 し 、 ア ド レス切 り換え回路 1 09 5は、 これを 0 P 3第 1 フ ェッチア ド レス回路 1 09 8 に供給する 。 この ア ド レス回路 1 09 8は、 この先頭要素ア ド レスを レジ スタ 1 0 1 1 に保持 し た後で 、 これを 8づっ増大させる こ と に よ り ベク ト ル Yのベ ク ト ル Δ 1 の要素のア ド レス を顕次生成 し 、 主記憶装置 Ί 1 1 に供給 し部分ベク ト ル Δ 1 の読み出 しを行う 。 この ア ド レスの更新は圧縮演算 装置 1 9 0か ら 、 そ こでの一つ のベ ク ト ル要素の処理ご と に与え ら れる信号 S E L Pに応答 して 、 + 8加算器 2 0 1 1 、 セ レ ク タ S E Lを用 いて行なわれる 。
    [0091] —方、 ア ド レ ス切換回路 1 09 5は、 汎用 レジス タ G P R ( R 2 + 2 ) か ら与え ら れるベ ク ト ル Zの先頭要 素の ア ド レスをその ま ま セ レ ク タ 4000に よ り 選択 し こ れを 0 P . 1 ス ト ア ア ド レ ス回路 1 09 6に供給す る 0 P . 1 ス ト ア ア ド レス回路 1 09 6は 、 この ア ド レ ス を レジス タ 1 00 5に と り 込み、 部分ベ ク ト ル厶 1 の圧 縮結果を書き込むためのア ド レス S A Rと して出力する 周様に部分べ ク 卜ル厶 2の圧縮結果をべ ク 卜ル Zの次の 要素位置に書き込む。 この ときの このス ト ア ア ド レスの 更新は 、 圧縮演算回路 1 9 0で一つ の部分ベ ク ト ルに対 する圧縮処理の終了 ご と に 出力 さ れる信号 U P S T A D Rに応答 し て + 8加算器 2 0 1 3、 セ レ ク タ S E Lを用 いて行なわれる 。 こ れ ら の回路の動作の詳細 は後に示す 。
    [0092] 第 9 図 は演算制御回路 1 0 4 の詳細 を示す 。
    [0093] 9 5 2 は 、 ア ド レス制御回路 1 1 0 内の前述 の O P .
    [0094] 2 フ ェッ チア ド レス回路 1 0 9 9 で第 2 オ ペラ ン ド と し て使用 さ れて いるベ ク ト ルの要素の ア ド レス が 、 生成さ れるの に同期 して そ の要素のイ ンデッ ク ス値を 出力 す る た め の、 O P . 2 実行要素 カ ウ ン タ である 。
    [0095] 同様に 9 5 0 , 9 5 1 はそれぞれ O P . 3 第 Ί フ ェ ツ チ ア ド レ ス回路 " 1 0 9 8 、 0 P . 3 第 2 フ ェ ツ チ ア ド レ ス 回路 1 0 9 7 に対応 し て 、 実行中 の要素の イ ンデッ ク ス値を生成す る 。 O P . 3 第 Ί 実行要素カ ウ ン タ 、 O P
    [0096] 3 第 2 実行要素 カ ウ ン タ で あ る 。
    [0097] カ ウ ン タ 9 5 0 , 9 5 1 . 9 5 2 はそ れぞれ 、 レ ジ ス タ 9 0 1 ， 9 0 4 , 9 0 2 と 、 そ れ ら の値を 、 + Ί す る + Ί 加算回路 を含 む 。
    [0098] 9 5 3 は 、 命令終了判定 回路で 、 第 2 オ ペ ラ ン ド と し て 指定さ れた ベ ク ト ル （ 今 の場合はベ ク ト ル X ) の す ベ て の要素の処理が 完了 し た か否か を判定 す る た め のも の で あ る 。
    [0099] す なわち 、 レジ ス タ 9 0 3 に保持さ れた 、 第 2 オ ペラ ン ド の ぺ ク 卜 ル要素の総数 と O P . 2 実行要素 カ ウ ン タ 9 5 2 が示す イ ンデッ ク ス値が一致す る か を比較器 9 0
    [0100] 4 で判定 す る こ と に よ り 上記処理の終了 を判定 す る 。
    [0101] 部分べ ク 卜 ル処理制御 回路 1 0 5 の構成を 第 Ί 3 図 に 示 す 。 部分終了判定回路 1 8 0は、 第 3オペラ ン ド と し て使 用 さ れる部分ベ ク ト ル ご と に 、 それにつ い ての処理が終 了 したか否かを判定する回路であ り 、 部分ベ ク ト ル処理 が終了 し た場合、 レジス タ 1 3 0 1 に " 1 " をセッ ト す る 。
    [0102] 圧縮処理の場合は 、 圧縮対象 とする一つ の部分べ ク 卜 ル （ た と えばベ ク ト ル Y .の 部分 ベ ク ト ル Δ 1 ) の す ベ ての要素につ いて の処理が終了 した ときに 、 部分べ ク 卜 ル処理終了 と判定する 。 ま た 、 完全終了判定回路 1 8 1 は主と し てマルチソ ー ト 処理のためのもので 、 圧縮処理 時に は上記 レジスタ 1 3 0 1 の出力 P V P E N Dに応答 し て部分べ ク 卜ルフ ェッ チ終了信号 P V F E N Dを出力 する 。
    [0103] 要素イ ンデッ ク ス生成回路 1 8 2は主にマルチソ ー ト 処理時に用 い ら れるもので圧縮処理の とき に は 、 主記憶 装置 1 1 1 か ら読み出 したベ ク ト ル Xの要素に含ま れる 圧縮処理対象部分べ ク 卜 ル （ た と えばべ ク 卜ル Yの部分 ベ ク ト ル厶 1 ) の 、 先頭要素のイ ンデッ ク ス値 T O Pを ア ド レス制御回路 1 1 0 と （ 演算制御回路 1 04と、 圧 縮演算回路 1 9 0へ供給 し 、 ま た 、 同時に読み出さ れた 末尾要素のイ ンデッ ク ス値 B T Mを圧縮演算回路 1 9 0 へ送出するのみである 。
    [0104] 8 3はマルチソ ー ト 処理時に使用 さ れる 、 処理方向 指定回路で あ り 、 こ の回路 につ いて は後にマルチソ ー ト 処理に 関連して説明 する 。 第 1 1 A図 は圧縮演算回路 1 9 0の構成を示す 。 部分 ベ ク ト ル判定回路 1 1 5 0に おい て 、 1 1 0 6はべ ク 卜 ル Yの先行す る要素 と後続の要素を比較す る た めの比較 器、 1 1 0 2、 1 1 0 7は部分べ ク 卜 ル Yの処理中 の要 素番号の イ ンデッ ク ス値 C T R 3 Pと 、 処理す べき部分 ベ ク 卜 ルの先頭要素番号のイ ンデッ ク ス値 T O P、 最終 要素番号 B T Mと の比較をそれぞれ行う 比較器であ り 、 1 1 0 4は 、 こ れ ら の比較器 1 1 0 6、 1 1 0 2 、 1 1 0 7の 出力 に応答 し て 、 処理中の部分ベ ク ト ルの中 に未 ソ ー ト 部分ベ ク ト ルがあ るかを検出 す る部分べ ク 卜 ル検 出論理であ る 。
    [0105] 部分べ ク 卜 ル指定 べ ク 卜 ル生成回路 1 1 5 1 は 、 部分 ベ ク ト ル判定回路 1 1 0 4の出力 に応答 し て 、 圧縮処理 の結果 と し て 出力 す べき ベ ク ト ル Zを 、 ベ ク ト ル Yの処 理中の要素に対す る イ ンデッ ク ス値 C T R 3 Pか ら 生成 す る回路で ある 。
    [0106] さ て 、 D E C信号を受け と つ た 命令制御回路 1 0 3 ( 第 8図 ） は フ リ ップフ ロ ップ 1 03 0の出力 をその ま ま 初期化を指示す る信号 I N I Tと し て ア ド レス制卸回 路 1 1 0 と 、 演算制御回路 1 0 4 と 、 部分べ ク ド ル処理 制御回路 1 0 5に送出する 。
    [0107] ア ド レ ス制御回路 1 1 0 ( 第 1 0図 ） で は 、 命令制御 回路 1 0 3 よ り 送 ら れた初期化信号 I N I Tの指示 に よ り 、 H用 レ ジ ス タ G P R ( R 2 ) に 格納 さ れた ベ ク ト ル Xの先頭要素ア ド レス （ こ れ ら を第 6 A図、 第 6 B図で は a 2 とする ） が セ レ ク タ S E Lを介 し て O P . 2 フ エ ツ チア ド レス回路 1 09 9内のア ド レス レジス タ 1 00 1 に セッ 卜 さ れ、 同様に、 汎用 レジスタ G P R ( R 2 + 1 ) , G P R ( R 2 + 2 ) か ら与えら れるべ ク 卜 ル丫 ， Zの先頭ア ド レス （ これら を a 3. a 1 とする ） は、 部 分べ ク 卜 ルア ド レス生成回路 1 05 1 内の ア ド レス レジ ス タ 1 00 2 , 1 003に セッ 卜 さ れる （ 第 6 A図① ） ， 演算制御回路 1 04 ( 第 9図 ） では、 命令制御回路 1 0 3 よ り 送ら れた初期化信号 I N I Tの指示に よ り O P 2実行要素 カ ウ ン タ 9 5 2内の カ ウ ン ト レジス タ 9 0 2 に " 0 " がセ レ ク タ S E Lを介 して セッ 卜 さ れる （ 第 6 A図② ） 。 さ ら に初期化信号 I N I Tに従い 、 汎用 レジ ス タ G P R ( R 1 ) に格納さ れたベ ク ト ル Xの要素数が 命令終了判定回路 9 5 3内の第 2オペラ ン ド要素数 レジ ス タ 9 0 3に セッ 卜 さ れる 。
    [0108] 部分べ ク 卜ル処理制御回路 1 0 5 ( 第 1 3図 ） では、 命令制御回路 1 0 3よ り 送られた初期化信号 I N I 丁 の 指示に よ り 、 部分処理終了 レジス タ （ P V P E N D レジ ス タ ） 1 3 0 1 が無条件に ' 1 ' に セッ 卜 され、 その後 部分処理終了信号 P V P E N Dが 3マシー ンサイ クルに わたっ て H I G H状態 と なる （ 第 6 A図③ ） 。
    [0109] 以上で初期化のプ ロ セ スが終了す る 。
    [0110] 初期化が終了 し たので 、 次に 、 ベ ク ト ル Xの先頭要素 の フ ェッチお よび圧縮処理が開始される 。 すなわち 、 命 令制御回路 1 0 3 ( 第 8図 ） か ら は I N I T信号の出力 後ベ ク ト ル Xに 対す る フ ェ ッチ要求信号 F T 2が記億装 置 1 1 1 に送出 さ れる 。 こ の と き 、 ア ド レ ス制御回路 ( 第 1 0図 ） の 0 Ρ . 2フ ェ ッ チア ド レ ス 回路 1 0 9 9 の 出力 は ベ ク ト ル Xの先頭要素ア ド レ スであ るので 、 主 記憶装置 1 1 1 か ら べ ク 卜 ル Xの先頭要素 （ 0. 4 ) が フ ェッ チデー タ F D R 2 と し て 読み出さ れる 。 こ の要素 の前半部は圧縮処理す べき 、 ベ ク ト ル Υの部分ベ ク ト ル 厶 Ί の先頭要素の イ ンデッ ク ス値 Τ〇 Ρを表 し 、 後半.部 は同 じ 部分 べ ク ト ルの末尾の要素の イ ンデッ ク ス値
    [0111] Β Τ Μを 表わ す 。 イ ンデッ ク ス値 T O Pと Β Τ Μは部分 ベ ク ト ル処理制御回路 （ 第 Ί 3図 〉 の要素イ ンデッ ク ス 生成回路 1 8 2 に送 ら れる 。
    [0112] 要素イ ンデッ ク ス生成回路 1 8 2 は 、 先頭要素イ ンデ ッ ク ス T 0 P ( こ の例で は 0で ある ） を 、 ア ド レ ス制御 回路 1 1 0 と 、 演算制御 回路 1 0 4 と 、 圧縮演算回路 Ί
    [0113] 9 0へ転送す る 。 末尾要素イ ンデッ ク ス値 B T Mは圧縮 演算回路 1 9 0へも送 ら れるデー タ ア ド レ ス制 ^ 回路 1
    [0114] 1 0 ( 第 1 0図 ） は 、 入力 さ れた イ ンデッ ク ス T O Pを ベ ク 卜 ル要素長 （ 8パイ 卜 ） だけ倍加 す るた め に シ フ 卜 演算器 2 0 9 4によ り 3 ビッ ト 分左 シ フ 卜 す る 。 さ ら に レ ジス タ 1 0 0 2 に すで に 保持 さ れて いる ベ ク ト ル Yの 先頭 ア ド レス （ a 3 ) と の加算を加算器 3 0 9 4で行 う ， こ う し て 、 部分 べ ク 卜 ル厶 Ί の先頭要素の ア ド レ ス が算 出 さ れる 。 こ の ア ド レ ス は レ ジ ス タ 1 0 0 4に セ ッ 卜 さ れる 。 セ ッ 卜 さ れた 部分 ベ ク ト ル Δ Ί の先頭要素 ア ド レ スは 、 セ レ ク タ 1 0 1 3を介 し て O P . 3第 1 フ ェッ チ ア ド レス回路 1 09 8内の レジス タ 1 0 1 1 にセッ 卜 さ れる （ 第 6 A図⑤ ） 。
    [0115] ここで 0 P . 2フ ェッチア ド レス回路 1 09 9の出力 F A R 2 と 、 演算制御回路 （ 第 9図 〉 内の O P . 2実行 ア ド レス要素 カ ウ ン タ 9 5 2のカ ウ ン 卜 碹 C T R 2が 、 べク 卜ル ）（の次の要素のフ ェッチに備えて更新さ れる ( 第 6 A図④ ） 。
    [0116] 一方、 演算制御回路 1 04 ( 第 9図 ） で は 、 部分終了 判定回路 1 8 1 ( 第 1 3図 ） よ り 入力 さ れる部分べ ク 卜 ル処理終了信号 P V P E N D Dに応答 して 入力 さ れたィ ンデッ ク ス値 T O Pを セ レ ク タ S E Lを介 して レジス タ 9 0 1 に初期値 と し て セッ ト さ れる 。
    [0117] —方命令制御回路 1 0 3は、 ベ ク ト ル Xの フ ェッ チ要 求信号 F T 2の 出力後べ ク 卜ル Yの フ ェッチ要求 F T 3 Pを 主記憶装置 1 1 1 に対 し て 3ク ロ ッ ク毎に送出 し始 める （ 第 6 A図⑥ ） 。
    [0118] 主記憶装置 1 1 1 は 、 フ ェッ チ要求 F T 3 Pに よ り 、 0 P . 3第 1 フ ェッ チア ド レス回路 1 09 8か ら の フ エ ツ チア ド レス F A R 3 Pに従い、 ベ ク ト ル Yの部分べ ク 卜 ル厶 1 の要素を出力 する 。 この よ う に して 、 願次べ ク ト ル Yの部分ベ ク ト ル厶 1 の要素が読み出さ れる 。 こ れ らの要素に対 し て 圧縮処理が次の よ う に行なわれる 。
    [0119] この圧縮処理で は読み出さ れたベ ク ト ル要素 （ 8パイ 卜 長 ） の後半 4パイ 卜 が等 し い 、 互い に 隣接す る要素群 を検出 す る 。
    [0120] 圧縮演算回路 1 9 0 ( 第 1 1 A図 ） に は 、 部分 べ ク 卜 ル厶 1 の要素が順次 フ ェッ チデ ー タ F D R 3 Pと し て供 給さ れ、 比較器 1 1 0 6に与え ら れる 。 比较器 1 1 0 6 は先に 読み出され、 すで に レ ジス タ 1 1 0 "! セ ッ 卜 さ れた要素 F D R 3 P Dと新た に読み出さ れた要素 F D R 3 Pを比較す る ためのものである が 、 部分べ ク 卜 ル厶 1 の第 0要素 につ いて は直前のべ ク 卜 ル要素がないた め比 較はな さ れない 。 比較器 1 1 0 2は 、 読み出 さ れた部分 べ ク 卜 ルの要素がそ の部分 べ ク 卜 ルの先頭要素か否かを 判別す る た め に 、 演算制御回路 （ 第 9図 ） の 0 P . 3第 1 実行要素カ ウ ン タ 9 5 0か ら 与え ら れるイ ンデッ ク ス 値 C T R 3 Pの値 と 、 要素 イ ンデッ ク ス生成回路 1 8 2
    [0121] ( 第 1 3図 ） か ら与え ら れた 、 部分 べ ク 卜 ル△ 1 の先頭 ベ ク 卜ル要素のイ ンデッ ク ス値 T 0 Pの値 （ こ の場合 は
    [0122] ' 0 ' ) を比較 し 、 比較結果を部分 べ ク 卜 ル検出 ^理 1 1 0 4へ入力 し て い る 。 新た に フ ェッ チさ れた要素 F D R 3 Pが部分 ベ ク ト ル 厶 1 の 第 0要素 で あ る 場 合 は 、 比較器 1 1 0 2の 出 力 が ' - ' を 示 す た め 、 第 1 1 B図の更番 5が選ばれ制御信号 S E L P , S T I N H の み出力 さ れ、 信号 S E T B A S E , S E T I N , S E L S T Dが出力 さ れな い （ 第 6図⑦ ） 。
    [0123] 制御信号 S E L Pは ア ド レ ス制御 回路 1 1 0 ( 第 Ί 0 図 ） と 、 演算制御 回路 1 0 4 ( 第 9図 ） に送出 さ れ部分 ベ ク ト ル厶 1 の次の要素の フ ェ ッ チの た め に 、 O P . 3 フ ェッ チア ド レ ス回路 1 09 8及び O P . 3第 1 実行要 素カ ウ ン タ 9 5 0にそれぞれア ド レスお よびイ ンデッ ク ス値の更新を指示する （ 第 6図⑧ ） 。
    [0124] 制御信号 S T I N Hは命令制御回路 1 03に送出さ れ ス 卜 ァ信号 S Tの発生を抑止する （ 第 6図⑨ ） 。
    [0125] 次に部分べ ク 卜 ル厶 1 内の 2番目 の要素である第 1 要 素がフ ェッ チされる と、 このフ ェッチに同期 して第 0要 素 （ 4， J U K U ) は レジス タ 1 1 0 1 にラッ チされる 比較器 1 1 0 6に よ り レジス タ 1 1 0 1 内の第 0要素 と 新た に読み出さ れた第 1 要素の比較が行なわれる 。 比較 は 8パイ 卜長のデー タ の う ち後半 4パイ 卜 につ いて なさ れる 。 比較の結果 （ この場合は両方 とも " J U K U " な ので比較結果は ' - ' ) は部分べ ク 卜 ル検出論理 1 1 0 4に送 ら れる 。
    [0126] 比較結果 （ ここで は ) と部分ベ ク ト ル状態 レジ ス タ 1 1 1 0の値 P V I N ( こ こで は ま だ部分ベ ク ト ル 処理状態にないか ら ' 0 ' である ） に応答 し て部分べ ク 卜 ル検出 IS理 1 1 04は、 未ソ ー 卜 部分ベ ク ト ルの開始 を検出す る 。 すなわち 、 第 1 I B図の項番 1 が選ばれ、 部分ベ ク ト ル処理状態セ ッ ト 信号 S E T I Nは H I G H 状態 と な り 、 信号 S E T B A S E , S T I N H ,
    [0127] S E L P ¾ H I G H状態 となる 。 信号 S E T I Nが H I G Hに なる と この信号がセ レク タ S E Lを介 し て部 分べ ク 卜 ル状態 レジス タ 1 1 1 0に部分ベ ク ト ル内の要 素の処理中であ る こ とを示す信号 と し て セ ッ ト さ れる ( 第 6 A図⑩ ） 。
    [0128] 信号 S E T B A S Eが " 1 " がな る と 、 部分べ ク 卜 ル △ Ί の先頭要素の イ ンデッ ク ス値 T O Pが 、 セ レ ク タ S E Lを介 し て 先頭位置 レジ ス タ 1 1 0 5 に セ ッ 卜 さ れ る '（ 第 6 A図⑩ ） 。
    [0129] 引続いて部分べ ク 卜 ル厶 1 の第 2要素が同 じよ う に処 理さ れる 。 こ の場合も比較器 1 1 0 6の 出力 は " 1 " で あ る が レ ジ ス タ 1 1 1 0の 出力 P V I Nが すで に " 1 " で あ る た め第 Ί Ί B図の項番 6が還ばれ 、 こ の場合 は信 号 S E I N , S E L P , S I N H Hは H I G H と な るが 信号 S E T B A S E は 0の ま ま であ り 、 レ ジ ス タ 1 1 0 5内の値 B A S E は変更さ れない 。 他 は項番 Ί の場合 と 同 じ で あ る 。
    [0130] こ こ で 、 未ソ ー 卜 部分 ベ ク ト ルの最終位置の検出 に つ い て 説明 す る 。 基本的 に は 比較器 1 1 0 6で 比較 す る 2 つ の ベ ク ト ル要素で不 一致が検出さ れた 時 に 、 前 の方の ベ ク 卜 ル要素を 部分べ ク 卜 ルの最終要素 と 判断 し 、 そ の イ ンデ ク ス値を ス ト ア す る こ とで こ れを実現す る 。
    [0131] た と え ば 、 第 3 A図の例 に お いて 部分べ ク 卜 ル厶 1 の 第 4要素 （ 5 , S E N A ) が フ ェッチさ れる と 、 そ の中 の キ ー 部分 と Ί つ 前 に フ ェッ チさ れた 、 レ ジ ス タ 1 1 0 1 内 の第 3要素 （ 7 , J U K U ) の キ ー 部分 と の比較が 比較器 1 1 0 6に よ り な さ れ て 不一致が検出 さ れて 、 そ の 旨 が部分べ ク 卜 ル検出論理 1 1 0 4に 入力 さ れる （ 第 6 A図 @ ) 。 こ の結果第 1 1 Bよ り 項番 3が選択さ れる こ の結果、 信号 S E L Pのみ Ί と な り 他は ◦ と なる 。 こ の とぎ レジス タ 1 1 6 2の出力 C T R 3 P Dは ' 4 ' と なっ て お り レジス タ 1 1 64の出力 C T R 3 P 2 Dは
    [0132] ' 3 ' となっ て いる
    [0133] レジス タ " I 1 6 1 と 1 1 6 3は タ イ ミ ング合わせのた めのちのである 。 今の例で は選択信号 S E L S T Dの値 ' 0 ' に従っ て現在フ ェッ チ し た要素の 1 つ前 に フ ェツ チ し た要素の イ ンデク ス値をラッ チする レジス タ 1 1 6 4の値 C T R 3 P 2 Dが セ レ ク タ Ί 1 6.0に よ り 還択さ れて部分べ ク 卜 ル厶 3の最終要素のイ ンデク ス値 ' 3 ' が ス 卜 ァデー タ レジス タ 1 1 '7 0の後半 4パイ 卜 の位置 に セ ッ 卜 さ れる 。 ま た部分べ ク 卜 ル△ 3の先頭要素の ィ ンデク ス値につ いて は先頭位置 レジス タ 1 1 0 5 にス 卜 ァ さ れた B A S E値 ' 0 ' が ス 卜 ァ デー タ レ ジ ス タ Ί 7 0の前半 4バイ ト に セ ッ 卜 さ れる 。 こ う し て 、 べ ク 卜 ル Zの第 0要素 （ 0 , 3 ) が生成さ れる 。 なお 、 レ ジ ス タ 1 1 6 5 は タ イ ミ ング合わせ に用 いて いる 。 こ れと同 時に制御信号 S T I N Hは L 0 Wと な り 、 命令制御回路 1 03 は この '結果、 抑止さ れて いたス 卜 ァ信号 S Tを H I G Hに し 、 （ 第 6 A図 ® ) ス 卜 アデ一タ レジス タ 1 1 7 0の値 （ 0 , 3 ) を主記憶装置 1 1 に ベ ク ト ル Z の第 0要素 と し て ス 卜 ァする 。 ス 卜 ァ はア ド レ ス制御回 路 1 0内の O P . Ί ス 卜 ァ ァ ド レ ス回路 1 0 9 6が示 す ア ド レ スに従がい行なわれる 。
    [0134] な お 、 レ ジス タ 1 1 6 0は 、 第 3 A図 の部分 べ ク 卜 ル Δ 1 の第 4要素が 、 た と えばそれが （ 5 , J U K U ) で あ る場合の ご と く 、 第 3要素 と 等 し い よ う な 特 別 の ケ ー ス に 対応 す る た め の も の で あ る 。 こ の 場合 、 部 分 べ ク 卜 ル厶 1 の最後に フ ェ ッ チ し た要素のイ ンデク ス値を 最終要素のイ ンデク ス値 と し て ス 卜 ァ する必要がある 。 この場合に は第 1 1 B図の項番 6が選ばれ、 信号
    [0135] S E T L S T Dの値を ' 1 ' と し て レ ジス タ 1 1 6 2の 値 C T R 3 P Dを最終要素の イ ンデッ ク ス と し て セ レ ク タ 1 1 6 0で選択 す る こ とで 、 こ れを可能 と し て い る 。
    [0136] 以上に おいて 、 部分べ ク 卜 ル Δ 1 の未ソ ー 卜 部分の先 頭要素が部分べ ク 卜 ル厶 Ί の先頭要素 と 一致 し た例 につ いて 述べ た がそ う でない場合に おいて 、 未ソ ー ト 部分の 先頭要素を検出 し た 場合も項番 1 の信号が出力 さ れ 、 同 様に し て 、 未ソ ー 卜 部分べ ク 卜 ルの検出を行い う る 。 但 し 、 こ の場合 、 未ソ ー 卜 部分べ ク 卜 ルの先頭要素の イ ン デッ グス値 は レ ジ ス タ 1 1 6 2の 出力 C T R 3 P Dに よ り 与え ら れる ので セ レ ク タ S E し ょ り こ れを選択 し て レ ジ ス タ 1 1 0 5に セ ッ 卜 する 。
    [0137] ま た 、 部分べ ク 卜 ル厶 1 の中 に未ソ ー ト 部分がない場 合 に は項番 2に し た がい処理さ れる が こ の場合、 べ ク 卜 ル Zの要素は生成さ れない こ と に な る 。
    [0138] ベ ク ト ル Zの ス ト ア に お いて O P . Ί ス ト ア ア ド レス 回路 1 0 9 6に よ り 出力 さ れる ア ド レ ス は以下の よ う に 定 め ら れる 。
    [0139] す なわ ち 、 初期化時 に レ ジ ス タ 1 0 0 3 に セ ッ ト さ れ たべ ク 卜 ル Zの先頭要素ア ド レス は 、 命令解読信号 I N S Tが圧縮命令に対 して は 0であるため 、 セ レ ク タ 4000に よ り選択され、 O P . 1 ス ト ア ア ド レス回路 1 09 6内のセ レ ク タ S E Lに送 られる 。
    [0140] この セ レク タ S E Lは初期化信号 I N I Tに応答 して この ア ド レスを初期化時に選択 し 、 レジスタ 1 005は こ れを取込む。
    [0141] その後圧縮演算回路 1 9 0か ら べ ク 卜 ル Zの要素の書 き込み ご と に 出力 さ れる信号 U P S T A D Rに応答 し て レジ スタ 1 00 5内のア ド レスを + 8加算器 2 0 1 3、 セ レク タ S E Lに よ り 8づっ更新する 。
    [0142] 次 に部分べ ク 卜 ル頜域 Δ 2 の圧縮処理への移行 につ い て説明す る 。 部分ベ ク トル△ 1 の最終要素 （ 5 , S E N Δ ) がフ ェッチさ れ、 上述の よ う に部分ベ ク ト ル Δ 3の 終了 が検出さ れて 、 部分べ ク 卜 ル指定情報 （ 0 , 3 ) と して O P . 1 にス ト アされる 。 こ の時、 制御信号
    [0143] S E L Pは H レ G H とな り 、 こ の信号に応答 して演算制 御回路 1 0 4 ( 第 9図 〉 内の O P . 3第 Ί 実行要素カ ウ ンタ 9 5 0の カ ウ ン ト 値 C T R 3 Pが更新される （ 第 6 図 @に
    [0144] これ と並行 し て圧縮演算回路 1 9 0 ( 第 1 1 A図 ） で は 、 信号 S T I N Hを遅延 し て ス ト ア ア ド レス更新信号 U P S T A D Rが生成さ れア ド レス制御回路 1 1 0 ( 第 1 0図 ） に送出さ れ、 その中の O P . Ί ス ト ア ア ド レス 回路 1 09 6は 、 ス ト ア ア ド レス S A Rを 、 この信号に 応答 し て イ ン ク リ メ ン 卜 す る （ 第 6図⑫ ） 。
    [0145] —方、 O P . 3第 1 実行要素カ ウ ン タ 9 5 0が出力 す る イ ンデッ ク ス値 C T R 3 Pは 、 部分終了判定 回路 1 0 6 (第 1 3図 〉 に送出さ れる 。
    [0146] 部分終了判定回路 1 0 6で は 、 圧縮命令の解読時に解 読回路 1 0 2よ り 与え ら れる信号 I N S Tが " 0 " であ る ため 、 セ レク タ S E Lが 、 ベ ク ト ル Xの第 0要素の読 み出 し の桔果得 ら れた 、 部分べ ク 卜 ル Δ 1 の最終要素の イ ンデッ ク ス値 B T Mを選択する 。 さ ら に 比較器 1 3 0 3 に よ り こ の要素番号 C T R 3 Pと こ のイ ンデッ ク ス値 B T Mを比較 し て （ こ の場合 は ' C T R 3 P > B T M ' と なる 〉 、 比較結果 に 従い部分処理終了 レ ジス タ 1 3 0 1 を H I G Hに セ ッ 卜 す る （ 第 6 A図⑬ ） 。
    [0147] 圧縮命令の場合は 、 部分ベ ク ト ル処理モ ー ド レ ジ ス タ 1 3 0 2 は解読信号 I N S Tが " 0 " で ある た め ' 0 ' に リ セ ッ 卜 さ れて い るか ら 、 レジ ス タ 1 3 0 1 の 出力 で あ る部分処理終了信号 P V P E N Dが H I G Hに な る と 同時 に ア ン ドゲー ト 1 3 0 6の出力で ある 完全処理終了 信号 P V F E N Dは H I G Hに な る （ 第 6 図<0) ) 。
    [0148] 完全処理終了信号 P V F E N Dは命令制卸回路 1 0 3 ( 第 8図 ） に送出 さ れる 。 命令制御回路 1 0 3はべ ク 卜 ル Xに対す る フ ェッ チ信号 F T 2の抑止を解除 し て 、 ベ ク 卜 ル Xの次の要素 に対 し て フ ェッ チ要求信号 F T 2を 主記憶装置 1 1 1 に送出 す る （ 第 6図 ® ) 。 こ う し て ベ ク 卜 ル丫 の次の部分べ ク 卜 ル厶 2 に対す る圧縮処理を開 始する 。
    [0149] 第 6 , 6 B図の タ イ ムチヤ一'卜 に示さ れる よ う に 、 3 ク ロ ッ グの ロ スのみで 、 この処理を開始する こ とが可 能 となる 。
    [0150] 最後にベク ト ル Xの最終べ ク 卜 ル要素 （ 今の場合第 1 要素 ） の処理が終了 し た場合につ い て説明する 。 こ の場 合、 O P . 2 実行要素カ ウ ン タ 9 5 2が示すイ ンデッ ク ス値 G T R 2が要素長 レ ジス タ 9 0 3内の値を超えた こ と が比較 9 0 4に判別さ れる 。 このため 、 完全処理終了 信号 P V F E N Dが完全終了判定回路 （ 第 1 3図 ） 1 0 7よ り 入力 さ れる と 、 ア ン ドゲー ト 9 05の出力で あ る 命令終了信号 M E N D 1 7 6が " 1 " とな り 、 命令制御 回路 1 03 ( 第 8図 ） に送出さ れ、 以後の フ ェッ チ及び ス 卜 ァ信号が抑止さ れて 、 圧縮命令の実行が終了す る 。
    [0151] 圧縮処理命令の終了後、 主記憶装置 1 1 1 に は第 3 A 図 のべ ク 卜ル Zが命令の第 1 オペラ ン ドべ ク 卜 ル と し て 得 ら れる 。 べ ク 卜 ル Zの各要素は部分べ ク 卜 ル厶 3 と 厶 4 のそれぞれの先頭要素の ィ ンデッ ク ス値 と末尾要素 のイ ンデッ ク ス値の対か ら な り 、 ベ ク ト ル Xに よ り べク ト ル Y上に指定さ れた部分ベ ク ト ル厶 1 , Δ 2 の各々 に おいてキー の値が重複する よ う な互い に隣接す る べ ク 卜 ル要素か ら なる部分べ ク 卜ル厶 3 , Δ 4 を示 し て いる 。 以上で圧縮処理命令の実現方法の説明を終える 。
    [0152] 次に 、 マルチソ ー 卜 命令実行時の第 Ί 図の装置の動作 の詳細を説明す る 。 マ ルチソ ー 卜 命令 は 、 圧縮命令 と 同 じ く 、 第 5 A 図 に 示 し た命令形式 を有す る 。
    [0153] 第 3 B 図 に例示す るマ ルチソ ー 卜 処理で は 、 ベ ク ト ル Z , Y , Wをそ れぞれ第 2 、 第 3 、 第 1 オペ ラ ン ド と し て 使用 す る 。 し た がっ て 引 用 レジス タ G P R ( R 1 ) 等 に は第 5 B 図の右列 に示 し たデ ー タ ま た は ア ド レ スがあ ら か じ め セ ッ 卜 さ れる 。
    [0154] 第 3 B 図の例で は 、 本実施例 に よ るマルチソ ー 卜 処理 で はべ ク 卜 ル Z が指定す る 、 ベ ク 卜 ル Y の 2 つ の部分 べ ク 卜 ル厶 3 に つ い て ソ ー 卜 が 完了 す る ま で ソ ー 卜 処理が 実行さ れる 。 ベ ク ト ル W は第 4 図 に示 し た よ う に そ の ソ 一 卜 処理の途中結果ベ ク ト ルを保持す る も の で あ る 。 部 分ベ ク ト ル厶 3 の ソ ー ト が 完了 す る と 、 引続い て 部分べ ク 卜 ル△ 4 に 対 し て 、 ソ ー 卜 処理が実行さ れる 。
    [0155] 第 7 図 は 、 第 3 B 図 に 示すマ ルチ ソ ー ト 処理 時の第 1 図 の装置の動作の タ イ ム チヤ一 卜 で あ る 。
    [0156] 第 4 図 に 関 し て 説明 さ れた よ う に 、 ベ ク ト ル Y の一 つ の部分 べ ク 卜 ル （ た と えば 、 Δ 3 ) のソ ー 卜 処理の場合 マ ー ジソ ー 卜 処理を 4 0 1 , 4 0 2 を操 り 返 し実行す る その際、 各マ ー ジソ ー ト 処理 、 た と えば 4 0 1 で は 、 部 分 ベ ク ト ル△ 3 を 、 そ の半分づつ の数の要素か ら な る 2 つ のべ ク 卜 ル に 分け 、 そ れ ら 2 つ の べ ク 卜 ル に マ ー ジ ソ 一 卜 処理 4 0 1 を施 し 、 桔果を ベ ク ト ル W に格納 す る 。 次のマ ー ジ ソ ー 卜 処理 4 0 2 で は 、 ベ ク ト ル Wを 2 つ の ベ ク ト ル に分け て マ ー ジ ソ ー ト 処理す る 。 し た がっ て 、 マ ー ジソ ー ト 処理時に は、 ソ ー ト されるべきベ ク 卜 ル Y 又は Wの内の 2つ の部分べ ク 卜 ルをフ ェッ チする必要が ある 。 ア ド レス制御回路 1 1 0 (第 1 0図 ） 内の 0 P . 3第 1 フ ェッチア ド レス回路 1 09 8、 0 P . 3第 2フ エッ チア ド レス回路 1 09 7が こ れ ら 2つのべク 卜ルの フ ェッチのためのア ド レスを生成するの に用い ら れる 。
    [0157] 0 P . 1 ス 卜 ァ ア ド レス回路 1 09 6は 、 ソ一 卜 の途 中結果をべ ク ト ル W又は Yに書込むた めのア ド レスを生 成す るの に用 い ら れる 。 なお、 O P . 2フ ェツチア ド レ ス回路 1 0 9 9はべ ク 卜ル Zの フ ェッチに用 いる。 この よ う に 、 ベ ク トル Y， Wか ら の読み出 し ァ ド レス 、 又は そ こへの書込みア ド レスをマ ー ジソ ー ト 処理 （ 40 1 等 ） ご と に 切 り かえる必要がある 。 こ れ ら の読み出 し ァ レ ス 、 書込みア ド レスの初期値を決め る のが 、 部分べ ク 卜 ル先頭ア ド レス生成回路 1 0 5 1であ り こ こで生成さ れ る ア ド レスを適宜切 り かえて ア ド レス回路 1 09 6〜 "！ 0 9 8へ供給するの が ア ド レス切 り 換え回路 1 09 5で' ある。 ま たマ ー ジソ ー ト 処理ご と にベク ト ル Yと Wの一 方をソ ー ト対象ベ ク ト ル と し 、 他方をソ ー ト 中間結果を 格納するベ ク ト ル とする よ う に 、 ソ ー ト対象べク 卜 ル と ソ ー 卜 結果格納べ ク 卜 ルを切 り かえる必要がある。 この 切り換えを指示す るのが部分べ ク ト ル処理制御回路 1 0 5 ( 第 1 3図 ） 内の処理方向指定回路 1 8 3である 。
    [0158] すで に述べた よ う に 、 各マ ー ジソ ー ト 処理た と えば 4 0 1 で は部分べ ク 卜 ル Δ 3を 2つ の べ ク 卜 ルに分けて ソ 一 卜 す る 。 こ のた め 、 部分べ ク 卜 ル△ 3を 2つ に 分 け た と きの 境 と な るべ ク 卜 ル要素の イ ンデッ ク ス値 M I Dを 決定す る の が 、 演算器 1 3 0 5で あ る 。 こ の M I Dの決 定 に は最小ソ ー ト 済要素長 S L N Gが 、 用 い ら れる 。 こ の値を保持す るの が レジ ス タ 1 3 03であ り 、 そ の値は + 1 加算器 2 3 0 3 に よ り 、 部分べ ク 卜 ル処理の終了信 号 P V. P E N Dが発生 さ れる たびに 更新さ れる 。
    [0159] 一方演算制御回路 1 0 4 ( 第 9図 ） 内の 、 O P . 3第 Ί 実行要素 カ ウ ン タ 9 5 0、 0 P . 3第 2実行要素 カ ウ ン タ 9 5 1 は 、 部分 べ ク 卜 ル処理制御 回路 1 0 5 ( 第 1 3図 ） 内の 、 O P . 3第 Ί フ ェ ッ チ ア ド レス 回路 1 0 9 8 、 0 P . 3第 2 フ ェッ チ ア ド レ ス 回路 1 0 9 6に よ り そ れぞれフ ェ ッ チ さ れる べ ク 卜 ル要素のイ ンデッ ク ス値 C T R 3 P , C T R 3 Sを カ ウ ン 卜 す る の に 用 い ら れる 第 1 2 A図 は ソ ー ト 演算回路 1 9 1 の 回路 図で 、 こ の 内 、 1 2 5 1 は 、 O P . 3第 Ί フ ェ ッ チ ア ド レ ス 回路 1 0 9 8 、 0 P . 3第 2 フ ェ ッ チ回路 1 0 9 7 ( いず れも 第 Ί 0図 ） に よ り 主記憶装置 1 1 1 か ら フ ェ ッ チさ れ た ソ ー 卜 す べき 2つ の べ ク ト ル にそ れぞれ属す る要素 F D R 3 P , F D R 3 Sの キ ー 部分を比較器 1 2 5 2で 比較す る こ と に よ り こ の 2つ のべ ク 卜 ルを ソ一 卜 す る も の で あ る 。
    [0160] 以上の説明 に お い て 、 第 4 図 に 示さ れた よ う に 、 ソ ー 卜 す べ き ベ ク ト ル （ た と え ばべ ク 卜 ル Y の部分べ ク 卜 ル Δ 3 ) を 2つ の ベ ク ト ルに 分 け 、 そ れ ら に マ ー ジ ソ ー 卜 処理 40 1 等を操返 し施す こ と 、 その繰返 し の際に 、 ベ ク 卜 ル Yと Wを入れかえて用いる こ とあるい は第 Ί 2図 のマ ー ジソ ー 卜回路 1 2 5 1 の動作 は本譲受人に讓渡さ れた米国出頃 S N , 68 5. Ί 1 6 ( Ί 9 8 4年 1 2月 2 1 出願） に開示された技術 と類似であ り この技術を参 照に よ り こ こ に組み込む。
    [0161] 第 4図で本実施例 に特徴的な点は 、 ベ ク ト ル Ζ内の、 各要素が指定する 、 先頭要素イ ンデッ ク ス T O Pと末尾 要素イ ンデッ ク ス B T Mに 基づき 、 ベ ク ト ル Y内の部分 べク 卜 ル （ た と えば厶 3 ) につ いて ソ ー ト 処理を施す こ と 、 さ ら に 、 部分べ ク 卜ル厶 3につ いて のソ ー 卜 が終了 すれば続いて ベク ト ル Zの次の要素が指定す る部分 べ ク 卜ル Δ 4 に対す るソ ー 卜 処理を実行する こ とであ る 。
    [0162] ま た 、 第 1 2 A図で本実施例 に特徴的な点 は 、 ソ ー ト 完了判定回路 1 2 5 0に よ り 、 マ ー ジソ ー 卜 処理 （ 第 4 図の 40 1 等 ） の操 り 返 し回数が所定値に な る前に 2つ のソ ー ト すべきベ ク ト ルのソ ー ト が完了 し た か否かを判 定 し 、 も し 完了が検出さ れれば 、 同 じべ ク 卜 ルにつ いて のマー ジソ ー 卜 処理を中止する こ とであ る 。
    [0163] さ て 、 マルチソ ー ト 命令が解読回路 1 0 2で解読さ れ る と各回路の初期化が 、 圧縮命令解読時 と同様 に なされ る 。 すなわち 、 O P . 2フ ェッ チア ド レス回路 1 0 9 9 ( 第 Ί 0図 ） 内の レ ジ ス タ 1 0 0 1 に ベ ク ト ル Zの先頭 要素の ア ド レス （ 第 7図で はこ れを a と示す ） がセ ッ 卜 さ れ、 部分べ ク 卜 ル先頭ア ド レス生成回路 1 0 5 1 ( 第 1 0図 ） 内の レジス タ 1 0 0 2 , 1 0 03 にそ れぞ れべ ク 卜 ル Yと Wの先頭 ア ド レス が セッ 卜 さ れる 。
    [0164] 第 1 3図の部分べ ク 卜 ル処理制御回路で は 、 圧縮処理 の場合 と同様 に 、 初期化信号 I N I Tに応答 し て 部分終 了判定回路 1 8 0か ら 出力 さ れる部分べ ク 卜 ル処理終了 信号 P V P E N Dが " 1 " と な り 、 こ れに応答 し て S し N Gレジ ス タ 1 3 03の入力 を切 り かえるセ レ ク タ S E し は初期値 " 0 " を選択す る 。 こ う し て先頭要素イ ンデ ッ ク ス生成回路 （ 第 1 3図 ） 内の S L N Gレ ジ ス タ 1 3 0 3 は初期値 ' 0 ' に セ ッ 卜 さ れる 。
    [0165] ま た 、 処理方向指定回路 1 8 3で は 、 同 じ 信号
    [0166] P V P E N Dに応答 し て 、 フ リ ップ フ ロ ップ 1 3 0 4が " 0 " に リ セ ッ 卜 さ れる 。 以上で初期化のステ ップが終 了 す る 。 O P . 2 フ ェッ チア ド レ ス回路 1 0 9 9 ( 第 1 0図 ） に よ り べ ク 卜 ル Zの最初の要素 （ 0 , 3 ) が主記 億装置 1 1 1 よ り フ ェッ チさ れる 。 こ の要素の先頭 4パ ィ 卜 はべ ク 卜 ル Yのソ ー 卜 す べき部分 べ ク 卜 ル Δ 3 の先 頭要素の イ ンデッ ク ス値 T O Pを表わ し 、 こ の要素の後 半 4パ イ 卜 はそ の部分べ ク 卜 ル厶 3の末尾のイ ンデッ ク ス B T Mを表わす 。 こ のベ ク ト ル Zの最初の要素に含 ま れる イ ンデッ ク ス値 T O Pと B T Mと 、 レジ ス タ 1 3 0 3内の最小ソ ー 卜 済要素長 S L N Gと か ら 、 要素イ ンデ ッ ク ス生成回路 1 8 2 ( 第 1 3図 ） 内の演算器 1 3 0 5 は 、 次の式 か ら 中間 イ ンデッ ク ス値 BTH - TOP 4- 1 + 2 SLNG
    [0167] HID = TOP + X 2 SLNG
    [0168] 2 SLNG+1
    [0169] J
    [0170] を求める 。 しこ しこでで L I 」 は 、 床関数を表わす 。 こ の M I Dは 、 ベク 卜 ル Yの部分べク 卜 ル厶 3を上位側 と 下位側の 2つ の部分ベ ク ト ルに分けてマ ージソ ー ト 処理 40 1 ( 第 4図 ） を施す ときの 、 下位側の第 2， 3要素 か ら なる部分 べ ク ト ルの先頭要素のイ ンデッ ク ス値を表 わ す 。 上位側の第 0 , 1 要素か ら なる部分ベ ク ト ルの先 頭要素の イ ンデッ ク ス値は T 0 Pに等 しい こ と はい う ま でちない。
    [0171] 要素イ ンデッ ク ス生成回路 1 8 2か ら T O Pと B T M が ア ド レス制御回路 1 1 0 ( 第 1 0図 ） 、 ソ ー 卜 演算回 路 9 1 (第 1 2 A図 ） と演算制御回路 1 0 4 ( 第 9図 ） へ送 ら れる 。 さ ら に B T Mは、 ソ ー ト 演算回路 1 9 1 ( 第 1 2図 ） に送 ら れ、 M I Dは部分終了判定回路 1 8 0へも送 ら れる 。
    [0172] ア ド レス制御回路 1 1 0 ( 第 1 0図 ） の部分ベ ク ト ル 先頭ア ド レス生成回路 1 0 5 1 で は 、 入力 さ れた イ ンデ ッ クス値 T O Pと レジス タ 1 0 0 2内 に初期値 と し てセ ッ 卜 されて いるベク ト ル Yの先頭要素ア ド レス （ 第 7図 で はこ れを aゥ と示す ） とか ら 、 3 ビッ ト左シフ タ 1 0 9 4、 加算器 0 9 4を用 いて 、 ベ ク ト ル Yの部分べ ク ル△ 3の 上位側部分ベ ク ト ルの先頭要素 （ イ ンデッ ク ス値 T O Pの要素、 今の場合は第 0要素 ） のア ド レスを 生成 し 、 レジ ス タ 1 004に セ ッ 卜 する 。 この ア ド レス は O P . 3第 1 フ ェ ッ チア ド レス 回路 1 0 9 8に よ り べ ク 卜 ル Yの上位側部分べ ク 卜 ルを フ ェッ チす る の に利用 さ れる 。
    [0173] 同様 に 、 入力 さ れた 中間イ ンデッ ク ス値 M I D と レ ジ ス タ 1 0 0 2内 のベ ク ト ル Yの先頭要素 ア ド レ ス と か ら 部分 べ ク 卜 ル厶 3の下位側部分べ ク 卜 ルの先頭要素 （ ィ ンデッ ク ス値 M I Dの要素 、 今の場合は第 2要素 ） の ァ ド レ スを 、 3 ピ ッ ト 左シ フ タ 3 09 4、 加算器 4 0 9 4 に よ り 生成 し 、 レ ジ ス タ 1 0 0 6に セ ッ 卜 す る 。 こ の ァ ド レ ス は,、 0 P . 3第 2 フ ェ ッ チ ア ド レ ス回路 1 0 9 7 に よ り べ ク 卜 ル Yの下位側部分べ ク 卜 ルを フ ェッ チす る の に 利甩 さ れる 。
    [0174] 一方 、 レ ジ ス タ 1 0 0 3 に あ る ベ ク ト ル Wの先頭要素 ア ド レ ス （ 第 7図で は こ れを a で表す ） と 、 入力 さ れ た イ ンデッ ク ス値 T 0 P と か ら 、 3 ビ ッ 卜 左 シ フ タ 2 0 9 9 、 加算器 3 0 9 9 よ り ベ ク ト ル Yの 、 部分 ベ ク ト ル △ 3の先頭要素 （ イ ンデッ ク ス値 T〇 Pの要素 、 今の 場 合 は第 0要素 ） に対応する 、 ベ ク ト ル Wの要素 （ 第 0要 素 〉 の ア ド レス を生成 し 、 レ ジ ス タ 1 0 1 0に セ ッ 卜 す る 。 こ の ア ド レ ス は O P . 1 ス 卜 ァ ア ド レ ス回路 1 0 9 6に よ り 、 ベ ク 卜 ル Yに つ い て のマ ー ジソ ー 卜 処理 （ た と え ば第 4 図の 4 0 1 ) の結果をべ ク 卜 ル W .に 秦 き込む の に 利用 さ れる 。
    [0175] 逆 に 、 第 4 図のマ ー ジ ソ ー 卜 処理 4 0 2の よ う に べ ク 卜 ル W上の部分 ベ ク ト ルを 上位側 と 下位側 の 2つ の部分 べ ク 卜 ルに分 けそ れにマ ー ジソ ー 卜 処理を施す た め に 、 次の よ う なア ド レスが部分べク 卜ル先頭ア ド レス生成回 路 1 05 1 によ り 生成さ れる 。 すなわち 、
    [0176] レ ジス タ 1 00 3に セッ 卜 さ れた ベ ク 卜 ル Wの先頭要 素ア ド レス と入力 された イ ンデッ ク ス値 T O Pとが 、 3 ビッ ト左シフ タ 2 09 5 と加算器 3 09 5を用 いて 、 ベ ク 卜 ル Wのマ ージソ ー 卜 すべき部分べ ク ト ルを 2つ に分 け て 得 ら れる上位側の部分ベ ク ト ルの先頭要素 （ イ ンデ ッ ク ス値が T O Pの要素 、 今の場合は第 0要素 ） の ア ド レスを算出し 、 レジス タ 1 00 7 に セッ ト する。
    [0177] こ の ア ド レスは 0 P . 3第 Ί フ ェッ チア ド レス回路 1 0 9 8 に よ り 、 処理 40 2の ご と く 、 ベ ク ト ル W上の部 分 べ ク 卜 ルに対 して マ ー ジソ ー 卜 処理を施す と き に利用 さ れる 。
    [0178] 同様に 、 レジ ス タ Ί 00 3に セ ッ ト されたベ ク ト ル W の先頭ア ド レス と 中間 イ ンデッ ク ス値 M I Dか ら 、 3 ビ ッ 卜 シ フ タ 2 0 9 8 、 加算器 3 09 8を利用 して 、 べ ク ト ル Wのソ ー 卜 すべき部分べ ク 卜ルを 2つ に分け た とき の下位側の部分ベ ク ト ルの先頭要素 （ イ ンデッ ク ス値が M I Dの要素、 今の場合は第 2要素 ） の ア ド レスを算出 し 、 レジス タ 1 0 08 に セ ッ 卜 される 。 こ の ア ド レスは 0 P . 3第 2フ ェッ チア ド レス回路 Ί 09 7 に よ り 処理 40 2の ご と く 、 ベ ク 卜 ル W内の部分べ ク ト ル に対 す る マ ージソ ー ト 処理を施す と き に利用 さ れる 。
    [0179] ま た 、 処理 40 2の よ う なマ ー ジ ソ ー ト 処理の洁果を べ ク 卜 ル Y内 に 格納す る た め 、 レ ジ ス タ 1 0 0 2内 の 、 ベ ク 卜 ル Υの先頭要素 ア ド レ ス と イ ンデッ ク ス値 T O P と か ら 、 3 ビ ッ 卜 シ フ タ 2 0 9 6、 加算器 3 0 9 6に よ り 、 ベ ク ト ル Υの部分べ ク 卜 ル （ Δ 3 ) の先頭要素 （ ィ ンデッ ク ス値が T O Pで あるもの ） の ア ド レスを算出 し レジ スタ 1 0 09 に セ ッ ト す る 。 こ の ア ド レ ス は 0 P . 1 ス 卜 ァ ア ド レス回路 1 09 6に よ り 後 に 利用 さ れる 。 さ て 、 第 1 3図 の処理方向指定 回路 1 8 3内の、 処理 方向を指定 す る フ リ ップ フ ロ ッ プ 1 3 0 4はすで に述べ た よ う に 、 初期値 0に セ ッ 卜 さ れて い る 。 こ の信号値 0 に 応答 し て 、 ア ド レ ス切 り 換え回路 1 0 9 5内 のセ レ ク タ 1 0 1 3 は 、 レ ジ ス タ 1 0 0 4に すで に セ ッ 卜 さ れた べ ク 卜 ル Yの部分べ ク ト ル厶 3の先頭要素 （ イ ンデッ ク ス値 T 0 Pの要素 ） の ア ド レ ス を遠択 し 、 O P . 3第 Ί フ ェッ チ ア ド レ ス 回路 1 0 9 8 に 供給 す る 。 同様 に 、 セ レ ク タ 1 0 1 4は 、 レ ジ ス タ 1 0 0 6に セ ッ 卜 さ れて い る 、 部分ベ ク ト ル Δ 3の 中 間要素 （ イ ンデッ ク ス値
    [0180] I Dの要素の ア ド レ ス を遠択 し 、 O P . 3第 2 フ ェツ チア ド レ ス回路 1 0 9 7 に 供給す る 。 同様 に セ レ ク タ 1 0 1 5 は 、 レ ジ ス タ 1 0 1 0に あ る 、 ベ ク ト ル Wの イ ン デッ ク ス値 T O Pの要素の ア ド レ スを選択す る 。 セ レ ク タ 40 0 0は命令解読信号 I N S Tがソ ー 卜 命令の解読 時に は " Ί " で あ る か ら セ レ ク タ 1 0 1 5か ら 出力 さ れ る 上記 ア ド レス を選択 し 、 0 P . Ί ス 卜 ァ ア ド レ ス 回路 1 0 9 6に送る 。 一方 、 命令制御回路 1 0 3 ( 第 8図 ） で は 、 マルチソ 一 卜 処理時に は 0 P . 3第 Ί フ ェッ チア ド レス回路 1 0 9 8 、 0 P . 3第 2フ ェッチア ド レス回路 1 0 9 7に対 応 じ て フ ェッ チ要素 F T 3 P , F T 3 Sを出力 する よ う に なっ て いる 。 こ う して 、 ベ ク 卜ル Yの部分べ ク 卜 ル △ 3の 、 上位側部分べク 卜ル と下位側の部分ベ ク トルの フ ェッ チが行なわれ、 それぞれで フ ェッチさ れた要素は フ ェッ チデ ー タ F D R 3 P , F D R 3 S と し て ソ ー ト 演 算回路 1 9 1 に与え ら れる 。
    [0181] 一方、 演算制御回路 " 1 0 4で は 、 ベ ク ト ル Zの先頭要 素 （ 0 , 3 ) が主記憶装置 1 1 1 か ら読み出さ れた とき に 、 要素イ ンデッ ク ス生成回路 1 8 2 ( 第 1 3図 ） か ら この要素が与え ら れ、 その前半の 4バイ 卜 が T O Pと し T O P . 3第 1 実行要素カ ウ ン タ 9 5 0に与え ら れ、 そ の後半 4ゾ ィ 卜 が B T Mと し て O P . 3第 2実行要素 力 ゥ ン タ 9 5 1 に 与え ら れ、 それ ら の カ ウ ン タ の初期値 と し て 利用 さ れる。 そ の後ソ ー ト 演算回路 1 9 1 で一対の ベク ト ル-要素'に対するソ ー ト がなさ れる たび に 、 そ こ か ら 出力 さ れる信号 S E L Pに応答 し て 、 それら の カ ウ ン タ の カ ウ ン 卜 値が更新さ れる 。
    [0182] なお 、 O P . 2実行要求要素カ ウ ン タ 9 5 2の動作は 圧縮処理の場合 と同 じである 。
    [0183] さ て 、 ソ 一 卜 演算回路 Ί 9 1 ( 第 Ί 2 A図 ） のマ ー ジ ソ ー ト 回路 1 2 5 "1 は 、 Ί 2 5 2は主記憶装置 Ί 1 1 か ら読み出さ れた一対 の ベ ク ト ル要素 F D R 3 P , F D R 3 S のそ れぞれの キ 一 部分を比較す る比較器で 、 1 2 5 4 は 、 マ ー ジ処理を制御 す る信号を発生 す るマ ー ジ論理 回路で 、 基本的に は 、 比較器 1 2 5 2 で の比較の 、 0 P . 3 第 1 フ ェ ツ チア ド レ ス回路 1 0 9 8 に よ り フ エ ッ チさ れた 、 べ ク 卜 ル Y の部分べ ク 卜 ル厶 の上位側の 部分ベ ク 卜 ルの要素 F D R 3 P と 、 0 P . 3 第 2 フ ェツ チァ ド レ ス回路 1 0 9 8 に よ り フ エツチさ れた 、 部分 べ ク 卜 ル△ 1 の下位側の部分べ ク 卜 ルの要素 F D R 3 S の 内 、 小さ い方を主記憶装置 1 1 1 に 格鈉 し 、 小さ い 方 の 要素 に つ づ く 要素 と 大き い方の要素を再度主記億装置 1 1 よ り フ エ ツ チ し 、 上 と 同 じ よ う に 比較 、 主記憶装置 1 へ の格納 を繰返す 。 マ一ジソ一 卜 回路 1 2 5 1 に は 、 フ ェ ッ チデ一タ F D R 3 P， F D R 3 S の そ れぞれ の ィ ン デッ ク ス値 C T R 3 P , C T R 3 S が演箅制御 回 路 1 0 4 ( 第 9 図 ） か ら 与 え ら れ、 さ ら に ィ ンデッ ク ス 値 T 〇 P , B T M , M I D . お よぴ最小ソ ー 卜 箨要素長 S し N G が要素ィ ンデッ ク ス生 成回路 1 8 2 か ら 与 え ら れ、 こ れ ら のデ ー タ を相互 に 比較 し て第 1 2 B 図 に 示す よ う な条件で 、 信号 S E し P , S T 1 N H を 出力 す る よ う に なっ て い る 。
    [0184] し のマ ー ジ ソ ー 卜 回路 "！ 2 5 1 の動作 は 、 前述 し た 米 国出願 S N 6 8 5 , 1 1 6 に 開示さ れた もの と類似で あ る た め 、 そ の詳細 は省略 す る 。
    [0185] な わ 、 la 'Ρ5 S E し Ρ はデ ー タ F D R 3 Ρ がデ ー タ
    [0186] F D R 3 S よ り 小さ い と き に Ί と な り 、 信号 S T I Ν Η は 、 通常は頂番 1 〜 6の ご と く 、 0である 。 信号
    [0187] S E丄 Pが Ί の と きセ レ ク タ 1 2 5 3 はデー タ F D R 3 Pを選択 し 、 ス ト アデー タ S D A T Aと し て 主記憶装置 1 1 1 に送る 。 こ の とき 、 信号 S T I N Hは通常 0であ るか ら 、 命令制御回路 1 03 ( 第 8図 〉 に よ り ス ト ア要 求信号 S Tが出力 さ れ、 上記デー タ はベ ク ト ル W内 に書 き込ま れる 。 この と きの書き込みア ド レスは O P . 1 ス 卜 ァ ア ド レス回路 1 0 9 6 ( 第 1 0図 ） に よ り 与え ら れ る 。
    [0188] ま た 、 こ の とき 、 ソ ー 卜 演算回路 1 9 1 は信号
    [0189] S T I N Hの値が 0である こ と に応答 し て 、 信号
    [0190] U P S T A D Rを 1 と し、 上記ア ド レス回路 1 09 6に ア ド レ ス の更斩を指示す る 。 一方、 信号 S E L Pが Ί の 場合第 Ί 0図 にお いて 0 P . 3第 Ί フ ェ ッチア ド レス回 路 1 0 9 8内の ア ド レス F A R 3 Pが更新さ れ、 部分べ ク 卜 ル厶 3の上位側 の部分べ ク ト ルの次の要素の読出 し に 用いる 。 一方 、 信号 S E L Pが 0の場合は 、 フ ェッ チ デー タ F D R 3 Sがセ レ ク タ 1 2 5 3に よ り 選択さ れ、 ス ト ア デー タ レジ ス タ 1 2 0 1 に セッ ト さ れた後ス ト ア データ S T D A T Aと し て主記憶装置；！ 1 に書き込ま れる 。 こ の際、 信号 S E L Pの値が 0である こ と に応答 し て 、 Q P . 3第 2フ ェ ッ チ ア ド レ ス回路 1 0 9 7 ( 第 1 0図 ） が生成す る ア ド レス F A R 3 Sが更新さ れる 。 こ う し て 、 部分ベ ク ト ル厶 3の下位側の部分 ベ ク ト ルの 次の要素の読み出 し が行なわ れ、 新た にマ ー ジソ ー ト が な さ れる 。
    [0191] さ て 、 第 Ί 2 Α図で ソ ー ト 完了判定回路 1 2 5 0は 、 本実施例 に特徴的な回路であ る 。 第 4図 に 示 し た よ う に マ ー ジソ ー ト 処理 40 1 , 40 2をソ ー ト 対象 と す るベ ク 卜 ル （ 第 4図で は部分べ ク 卜 ル厶 3又は厶 4 ) の要素 数に 依存 し て き ま る一定回数だけ橾 り 返せばソ ー 卜 が 完 了 す る こ と が分かっ て いる 。
    [0192] し か し なが ら 、 上記一定回数だけマ ー ジ ソ ー ト 処理を 繰 り 返さ な く て も ソ ー ト が完 5 了 し て し ま う こ と が あ る 。
    [0193] 7
    [0194] こ こで ソ ー 卜 完了 と は 、 ソ ー ト 後のデ ー タ 列が あ ら か じ めき め た値の顒 、 （ 本実施例で は ア ルフ ァ べッ 卜 の昇 m ) に なっ て いる こ とで ある 。 こ の際 、 同 じ 値 の相 隣る
    [0195] 2つ の デ ー タ は ア ル フ ァ ベ ッ ト の 昇顒 に な っ て い る と み な す 。
    [0196] こ の よ う な場合 、 ソ ー ト 完了 が検出さ れればマ ー ジ ソ 一 卜 処理を無用 に 繰 り 返す必要はない 。 以下 、 ソ ー ト 完 了 の具体的方法 に つ い て 説明 す る 。
    [0197] ソ ー 卜 す べ き アデ タ が すで に 昇願に ソ ー 卜 さ れて い るか否か は ス ト アデー タ レ ジ ス タ 1 2 0 7 内 の キ ー 部分 と Ί つ前のサ イ ク ル に フ ユツ チさ れた ァ デ ー タ を保持す る レ ジ ス タ 1 2 0 2内の キ ー部分を比較器 1 2 0 3で比 較す る こ と に よ り 行なわ れる 。 比較の結果 、 前者が後者 よ り 大きけ ればソ ー 卜 未完了 信号 F E N D Pが 完全終了 判定回 路 Ί 0 7 ( 第 1 3 (1〉 内 の演算モ ー ド フ リ ッ プ フ ロ ップ Ί 3 0 2 に ア ン ド ゲ ー 卜 5 0 0 0を介 し て 送 ら れ る 。
    [0198] こ のア ン ドゲー 卜 5 0 0 0 の他方の入力 は命令解読信 号 I N S Tであ り 、 この信号はマルチソ ー 卜命令に対 し て は " 1 " である 。 こ う し て 、 ソ ー ト が未完了の とき に は こ の フ リ ップフ ロ ップ 1 3 0 2 がセッ ト状態に なる ( 第 7 図⑧ ） 。 部分終了判定回路 1 8 0 に は 、 部分べ ク ト ル厶 1 の上位側部分べ ク 卜 ルの要素のイ ンデッ ク ス値 C T R 3 P 、 下位側部分ベ ク ト ルの要素のイ ンデッ ク ス 値 C T R 3 S が演算制御回路 1 0 4 ( 第 9 図 ） か ら与え ら れて いる 。 一方、 要素イ ンデッ ク ス生成回路 1 8 2 ( 第 1 3 図 ） から 与え ら れた 中間イ ンデッ ク ス値 M I D か ら滅算器 5 0 2 0 に よ り 生成さ れた M I D — Ί がセ レ ク タ S E L に よ り 選択さ れ、 比較器 1 3 0 3 において ィ ンデッ ク ス値 C T R 3 P と比較さ れる 。 一方イ ンデッ ク ス値 C T R 3 S と イ ンデッ ク ス値 B T Mが比較器 1 3 0 6で比較さ れる 。
    [0199] 部分べ ク ト ル△ 3 に対する 1 回のマ ー ジソ ー ト 処理が 進行 し 、 C T R 3 P > M I D — Ί かつ C T R 3 S > B T Mが比较器 1 3 0 3 と 1 3 0 6 に よ り 検出される と A N Dゲ ー 卜 5 0 4 0 の出力 に よ り 部分終了 レジス タ Ί 3 0 1 が セ ッ 卜 さ れ、 部分終了 信号が H I G H になる ( 第 7 図⑨ ） 。 し か し こ の場 合、 部分ベ ク ト ル演算モ ー ドフ リ ップ フ ロ ップ 1 3 0 2 が H I G Hであ るため 、 ァ ン ドゲ一 卜 1 3 0 6 の 出力 は 0 と な り 、 完全終了信号 P V F E N D は出力 さ れない 。 （ 第 7 図⑬ 〉 した がっ て こ の部分 べ ク 卜 ル に 対 す る ソ一 卜 処理 を く り 返 し行 う 必 要が あ る こ と が示さ れる 。
    [0200] 一方、 要素イ ンデッ ク ス生成回路 1 8 2内 の ソ ー ト 済 要素長 S L N G ( 1 3 0 3 ) は 、 部分処理終了信号 P V P E N Dに よ り イ ン ク リ メ ン 卜 さ れ、 レ ジ ス タ 1 3 0 3の出力 S L N Gは ' Ί ' と な る （ 第 7図 © ) 。 ま た 処理方向指定信号回路 1 8 3内 の フ リ ップ フ ロ ップ 1 3 0 4に 接続さ れた A N Dゲ ー 卜 群 は 、 部分処理終了信号 P V P E N Dが " 1 " に な り 完全終了信号 P V F E N D が " 0 " で あ る こ と か ら 、 こ の フ リ ップ フ ロ ッ プを セ ッ 卜 状態 に し 、 こ の結果信号 E X D I Rは 1 と な り 、 （ 第 7図⑰ ） 、 次のマ ー ジ ソ ー ト 処理 （ 第 4図 4 0 2 ) に 備 え る 。
    [0201] ま た 、 モー ド フ リ ップ フ ロ ップ Ί 3 0 2は 、 部分べ ク 卜 ル処理終了信号 P V P E N Dを遅延 し た 信号
    [0202] P V P E N D 2 Dに よ り リ セ ッ 卜 さ れる 。
    [0203] ア ド レ ス制御 回路 Ί 1 0 (第 Ί 0図 ） の ア ド レ ス切 り 換え回路 1 0 9 5 は処理方向指定信号 E X D I Rの値が 1 で あ る こ と に 応答 し て セ レ ク タ 1 0 1 3 . 1 0 1 4 , 1 0 1 5 に よ り そ れぞれ O P . 3第 Ί フ ェ ッ チ ア ド レス 回路 1 0 9 8 に 、 レ ジ ス タ 1 0 0 7の内容を 、 O P . 3 第 2フ ェ ッ チア ド レ ス回路 1 0 9 7 に 、 レ ジ ス タ Ί 0 0 8の 内容を 、 O P . 1 ス 卜 ァ ア ド レ ス回路 1 0 9 6に 1 0 0 9 の内容を供給 す る 。 そ れ ら の ア ド レ ス はそ れぞれ の 回路内 の ア ド レ ス レ ジ ス タ 1 0 , 0 2 , 1 0 T 3 に 、 部分処理終了信号 P V P E N Dに応答 し て セ ッ 卜 さ れる 。 （ 第 7図⑩ ） 。
    [0204] 演算制御回路 1 0 4 ( 第 9図 ） で は、 部分処理終了信 号の 0. 5ク ロ ッ ク遅れの信号 P V P E N D Dに応答 し て カ ウ ンタ 9 5 0 , 9 5 1 の初期値 と してそ れぞれ T O P , M I Dをセッ 卜 する 。
    [0205] 以上の過程を経て部分べ ク 卜 ルの処理方向が切 り 換え ら れて 、 3 ク ロ ッ ク 後に は第 2回 目 のマ ー ジソ ー 卜 処理 40 2 ( 第 4図 ） が開始さ れる 。 こ のマー ジソ ー ト に対 し ては部分べ ク 卜 ル厶 3内のソ ー 卜 完了判定回路 Ί 2 5 0 ( 第 1 2 A図 ） か ら はソ ー ト 未完了信号 F E N D Pが 出力 さ れない 。 し た がっ て フ リ ップ フ ロ ップデー タ がソ 一 卜 済み と な り 、 モ ー ド 1 3 0 2が リ セ ッ ト 状態の ま ま であ る 。 そ の状態で部分処理終了信号 P V P E N Dが レ ジ スタ 1 3 0 1 か ら 出力 される と 、 A N Dゲー ト 1 3 0 6か ら 完全処理終了信号 P V F E N Dが出 力 さ れて 、 圧 縮命令の場台 と同様 に次の部分べ ク ト ル指定情-報の フ エ ツ チがなさ れる 。 以上で部分べ ク 卜 ルに対するマ ー ジソ 一 卜 処理の終了が如何に検出さ れるか につ いて の説明を 終える 。
    [0206] マルチソ ー ト 命令の処理がす べて終了後 、 主記憶装置 1 1 1 に は第 3 B図のベ ク 卜ル 2 1 2がソ ー 卜結果 と し て 得 ら れる 。 図か ら分 かる よ う に べ ク 卜 ル 2 Ί 2の部分 べ ク 卜 ル△ 3 , △ 4内の要素はソ ー 卜 済み と なっ て い る 以上の圧縮処理 とマルチソ ー ト 方法を用 いる こ と に よ 89/
    [0207] 61 り 、 ベ ク ト ルプ ロ セ ッ サ に よ り 定 め ら れた デ ー タ 長 を こ え る長さ のキ ー群を べ ク ト ル処理に よ り ソ ー 卜 で き る 。
    [0208] この際キ ー の先頭か ら ソ ー 卜 処理可 能なデ ー タ 長を単 位 に部分キ ー を切 り 出 し て ソ ー 卜 処理を行い 、 未ソ ー 卜 5 の部分を捜 し て 再ソ ー 卜 が必要な レ コ ー ド群 に対 して の み上記過程を く り 返 し て ソ ー 卜 を進める手法を とつ た 。 従っ て キ ー を ある 時点 ま で参照 し て レ コ ー ド の大小関係 が決定 す る と 、 キ ー の残 り の部分 につ い て は参照を行 う 必要が な く 、 長い キ ー の全体を参照す る こ と に よ る効率
    [0209] 1 0 低下が回避でき る 。
    [0210] 例 えば 、 す べて のキ ー の大小関係がキ ー先頭の 4 パ イ 卜 で 決定 す る よ う な極端な例 を と れば 、 本実施例ソ ー 卜 処理方式 はべ ク 卜 ル命令 に よ る ソ ー 卜 処理を Ί 度 し か実 行 し ない 。 従っ て キ ー 長に 依存 し な い性能を得る こ と が
    [0211] 1 5 で き る 。
    [0212] 次に本実施例のマ ルチソ ー 卜 処理の効果を定量的に示 す 。 比較の対象 と し て 従来のベ ク ト ル計算機 と し て 日 立 製作所製 " M 6 8 0 H コ ン ピュ ー タ の た めの内蔵デー タ ベ ー スプ ロ セ ッサ " を用 い る 。
    [0213] 20 マルチソ ー 卜 の対象 と なる個々 の部分べ ク 卜 の要素 数の平均 を m 、 部分ベ ク ト ルの個数を n z m と す る と 、 ベ ク ト ル命令 の セ ッ ト ア ップ時 間を a と し 、 マルチソ ー 卜 に お け る部分 べ ク 卜 ルの切 り 換 え に 要 す る ク ロ ッ ク 数 を b と す る と 、 ソ ー ト 処理時間 は次の よ う に な る 。 _ n
    [0214] 従来型計算機 ： n log m + ( 一 log m ) x a
    [0215] m
    [0216] n
    [0217] 本 実 施 例 ： n og m + ( — log m ) x b
    [0218] m し 、 上記パラメ一タ して
    [0219] 3
    [0220] m = 2 0 , n = 0 a = 5 0 , b = 1
    [0221] と し た場合に 、 従来型計萼機— o
    [0222] 本実施例 . 0 . 0 とな り 、 約 3倍の高速化が図れる 。 さ ら に こ の比較にお いて は 、 従来型計算機で は必須の処理である 、 複数の部 分ベ ク ト ル指定情報を顕次 と り 出 して 、 ベ ク ト ル命令起 動の た めの命令の セッ 卜 ア ップを行う 等のス カ ラ命令列 の実行時簡を考慮 し て いない 。 こ れを考えれば 、 本実施 例の加速率はさ ら に高く なる ことが考え ら れる 。 なお 、 本実施例で は部分べク 卜ル指定ベ ク ト ルの要素 と し て先頭処理要素と最終処理要素の イ ンデ ク ス値の対 を用 いたが 、 先頭処理要素のイ ンデク ス値 と部分べ ク 卜 ル内の要素数の対を用 いる こ と も可能である 。
    [0223] ま た部分ベ ク ト ル内のソ ー 卜 処理を実現する演算装置 と し て 、 前述の米国出顦 S N . 6 8 5 , Ί 1 6に示され るマ ー ジソ ー ト 処理方式を適用 す る方式を とつ たが 、 特 願昭 6 2 — 0 8 6 8 4 6 に示さ れる自然マ ー ジソ ー ト 処 理方式を適用 する こ とも可能で ある 。 この場合、 自然マ ー ジソ ー ト 処理の実行に伴う 処理モ ー ドの切 り 換え回数 を本実施例の ソ ー 卜 完全終了信号 N D P と し て 用 い れば よ い 。
    [0224] 本発明 に よ れば 、 ソ一 卜 可 能なデー タ 長に $ij限のある べ ク 卜 ル処理装置に おいて 、 任意長の固定長キ ー デー タ の ソ ー 卜 を実現す る こ と が可能 と なる 。 ま た非数値演算 の べ ク 卜 ル化に おい て頻出す る 、 あるべ ク 卜 ル上の複数 の部分頜域 （ 部分べ ク 卜 ル 〉 に対 し て 、 こ れ ら を検出 し 部分 べ ク 卜 ル指定情報 と し て べ ク 卜 ルデ ー タ の形で生成 す る機構が与 え ら る 。 ま た 生成さ れた部分 べ ク 卜 ル指定 情報か ら な る べク 卜 ルデ ー タ を入力 し て 複数の部分 ぺ ク 卜 ルを一括 し て べ ク 卜 ル処理する こ と が可能 と な る 。
    权利要求:
    Claims請 求 の 範 囲
    1 . 記憶装置に格納さ れたベ ク ト ルを） i次読み出 し 演算するベ ク トル処理装置に おいて 、 入力 ベク ト ル中で あ る特定の条件をみたす連続するベ ク ト ル要素につ いて 該連続するべク 卜ル要素から構成さ れる前記入力 べ ク 卜 ルの部分領域の開始 と終了を検出す る手段 と 、 開始検出 時に該部分領域の先頭べ ク 卜 ル要素の位置情報を保存す る手段 と 、 終了検出時に最終ベ ク ト ル要素の位置情報を 前記保存さ れ fc先頭べ ク 卜 ル要素の位置情報 と 共に 、 前 記記憶装置に格納する手段 と を設 た こ と を特徴 とす る べ ク 卜 ル処理装置。
    2 . 前記第 Ί 項のベ ク ト ル処理装置に おいて 、 そ の 部分頜域検出手段が 、 順時読み出さ れる ベク トル要素の 各各 につ いて 、 各べ ク 卜 ル要素が特定条件 を満足するか 否かを判定する部分領域内 べ ク 卜 ル要素判定手段 と 、 ぺ ク 卜ル処理の任意の時点で部分領域内の べ ク 卜 ル要素の 処理中であ るか否かを示す部分領域検出状態記億手段 と か ら な り 、
    部分領域検出状態記憶手段が部分領域内の ベグ卜 ル要 素の処理中でない こ と を示 し 、 かつ前記部分頜域内べ ク 卜 ル要素判定手段が前記特定条件をみた して いる こ と を 示す ベ ク ト ル要素を検出 し た 時に 、 前記部分領域検出状 態記億手段を部分領域内のべ ク ト ル要素の処理状態に あ る こ と を設定す る と 同時に部分領域の開始が検出さ れ 、 前記部分領域検出状態記憶手段が部分頜域内 の ベ ク 卜 ル要素の処理中で あ る こ と を示 し 、 かつ前記部分領域内 べ ク 卜 ル要素判定手段が前記特定条件を みた し て いない こ と を示す ベ ク 卜 ル要素を検出 し た 時 に 、 前記部分領域 検出状態記憶手段を部分領域内のベ ク 卜 ル要素の処理状 態に ない こ と を設定する と同時に 部分領域の終了が検出 さ れる こ と を特徴 と する べ ク 卜 ル処理装置。
    3 . 前記第 2 項のベ ク ト ル処理装置 に おい て 、 そ の 特定の条件 と は頤次読み出さ れた べ ク 卜 ル耍素の各 々 に つ い て 、 Ί つ 前の ベ ク ト ル要素 と等値関係で あ る こ と を 特徴 と す るべ ク ト ル処理装置。
    4 . 複数の ベ ク ト ル要素か ら な る第 Ί の ベ ク ト ル と 各要素が該第 Ί のべ ク 卜 ル内の Ί つ あ る い は互い に 隣接 す る複数の べ ク ト ル要素か ら なる 部分領域を指定 す る部 分領域指定情報で あ る第 2 の ベ ク ト ルを 記億す る装置 と 該記憶装置か ら 第 1 、 第 2 の べ ク 卜 ルの要素を顒次読 み出す 第 1 、 第 2 の読み出 し手段 と 、 第 Ί の読み出 し 手 段 に よ り 顚次読み出 さ れる べ ク 卜 ル要素 に対 し て 所定の 演算処理を行 う 演算手段 と 、 該演算手段 に よ り 顒次生成 さ れた 演算結果を前記記憶装置に順次書き込みを行 う 手 段 と 、
    第 2 の読み出 し 手段か ら 読み出さ れた 部分領域指定情 報か ら 、 第 1 の べ ク 卜 ル内 の部分領域 に対 す る 読み出 し 開始位置情報 と読み出 し終了位置情 報 と 演箅結果の書き 込 み位置情報 を生成 す る部分頜域ア ク セ ス情報生成手段 と 、
    第 Ί の読み出 し手段につ いて 、 読み出さ れるべ ク ト ル 要素の位置情報を読み出 し に周期 し て 出力 す る部分領域 読み出 し位置情報供給手段 と 、
    該部分領域読み出 し位置情報供給手段の出力 する部分 領域内のべ ク ト ル要素の位置情報 と前記部分領域ァ ク セ ス情報生成手段の出力 する読み出 し終了位置情報 と を比 校 し て 、 部分領域への演算処理の終了を検出す る部分頜 域処理終了判定手段 とを有 し 、
    前記第 2 のベ ク ト ルか ら読み出さ れた べ ク 卜 ル要素を 前記部分領域ア ク セ ス情報生成手段に入力 し 、 出力 さ れ た部分領域読み出 し 開始位置情報を前記第 Ί の読み出 し 手段に セッ 卜 し 、 演算結果書き込み位置情報を前記書き 込み手段に セッ 卜 し た後、 頌次読み出さ れる第 1 の べ ク 卜 ル内 の部分領域のべ ク 卜 ル要素に前記所定の演算処理 を施 し 、 前記部分領域処理終了判定手段が該部分領域へ の処理終了 を検出する毎に 、 第 2 の読み出 し手段を制御 す る こ と を特徴 とす るべ ク 卜 ル処理装置。
    5 . 前記第 4 項のべ ク 卜 ル処理装置において 、 その 部分領域指定情報 と して 、 該部分領域内の先頭ベク ト ル 要素への読み出 し カ ウ ン タ の値 と最終べ ク 卜 ル要素への 読み出 し カ ウ ン タ の値の対を用 いる こ と を特徴 とす るベ ク 卜 ル処理装置。
    6 . 前記第 4 項のベ ク ト ル処理装置に お いて 、 部分 領域ア ク セ ス情報生成手段の 出力 を記億する部分領域ァ ク セ ス情報記憶手段 と 、
    部分頜域内のベ ク 卜 ル要素に対す る所定の演算処理の 結果に基き 、 該部分領域内のベ ク ト ル要素へ の演算を操 り返 し実行す る必要があ るか否かを示す部分領域再演算 実行要求判定手段 とを有 し 、
    部分領域処理終了判定手段が部分頜域内のぺ ク ト ル要 素へ の処理終了 を検出する毎に前記部分領域再演算実行 要求判定手段の判定結果を参照 し 、 該部分領域への再演 算が必要で ある場合には 、 前記部分頜域ア ク セ ス情報記 憶手段の保持す る部分領域の読みだ し開始位置情報 と読 みだ し終了位置情報、 及び書き込み位置情報に従い 、 第 1 の読み出 し 手段の有す る ア ド レ ス レ ジ ス タ と書き込み 手段の有す る ア ド レ ス レジ ス タ を更新 し 、 該部分領域へ の演算を再実行す る こ と を特徴 と する べ ク 卜 ル処理装置
    7 . 前記第 6 項のベ ク 卜 ル処理装置に おい て 、 その 部分領域再演算実行要求判定 手段 と は該部分頜域内のべ ク 卜 ル要素が ソ ー 卜 さ れて いるか否かを判定す る手段で あ り 、 ソ ー ト さ れて い ない場合 に再演算実行の要求を行 う こ と を特徴 と す るべ ク 卜 ル処理装置。
    8 . 各々 がソ ー 卜 対象 と な るキ ーデ ー タ 要素を含む レ コ ー ドデー タ 要素を一定 ま た は不規則な ア ド レス簡隔 で保持するデ ー タ 記憶装置 と 、 前記キ ー デー タ 要素の有 す る要素長に はみた ない要素長デ ー タ の ソ ー 卜 命令を有 す るデ ー タ 処理装置に おい て 、 前記各 レ コ ー ド デ ー タ 要 素の記憶装置内で の ア ド レ ス情報か ら な る ベ ク ト ルを 用 いて 、 各 レコ ー ドデー タ 要素に つ い て各々 が含む各キ ー デ ー タ 琴素の先頭か ら前記ソ ー ト 命令のソ ー ト 可能な要 素長に相当 する長さ のデー タ を部分キーデー タ と し て読 み出 し 、 レコ ー ドデー タ 要素 1 つ につき Ί つ の割合いで 読み出さ れた部分キーデー タ の各々 について該部分キ ー デー タ と これを含む レコ ー ドデー タ要素の ア ド レス情報 とを対に して 、 該対デー タ の一群を要素デー タ が一定の ァ ド レス間隔で配置さ れるべ ク ト ルの形式に従っ て 前記 記憶装置内 に配列 し 、
    該対デー タ か ら な るベ ク ト ルを 、 対デー タ の 含む部分 キー デー タ の値に従っ てソ ー ト し 、
    ソ ー 卜 結果のべ ク 卜 ルにつ いて 隣接するべ ク ト ル要素 で各々 が含む部分キ ー デー タ の値が等 しいものを未ソ ー 卜 部分領域 と し て検出 し 、
    検出さ れた複数の未ソ ー ト 部分領域に対し て 、 各未ソ 一 卜部分領域内の未ソ ー 卜 べ ク 卜ル要素につ いて 該べ ク 卜ル要素内 の レ コ ー ドデー タ 要素ア ド レス情報をも と に キ ーデー タ ー要素を参照 し 、 該キーデー タ 要素内か ら前 に読み出 し た部分キー デー タ の直後の部分キー デー タ を 読み出 し て前記未ソ ー ト ベ ク ト ル要素の部分キ一デー タ の値を書き換え 、
    全て の未ソ ー 卜 べク 卜 ル要素が書き換え ら れた未ソ ー 卜 部分領域につ いて再びソ ー 卜 及ぴ未ソ一 卜 部分領域の 検出を緩り 返 し適用 し 、 未ソ ー 卜部分領域の消滅を もつ て ソ ー 卜 を完了する こ と を特徴 と す るソ ー ト 処理方法。
    类似技术:
    公开号 | 公开日 | 专利标题
    US20180137416A1|2018-05-17|Methods and systems for data analysis in a state machine
    US9535861B2|2017-01-03|Methods and systems for routing in a state machine
    JP6181074B2|2017-08-16|ステートマシンにおける検出方法とシステム
    KR101873619B1|2018-07-02|상태 기계 격자에서의 불리언 로직
    Rau et al.1981|Some scheduling techniques and an easily schedulable horizontal architecture for high performance scientific computing
    US5687360A|1997-11-11|Branch predictor using multiple prediction heuristics and a heuristic identifier in the branch instruction
    US5165023A|1992-11-17|Parallel processing system with processor array and network communications system for transmitting messages of variable length
    EP0459192B1|1998-03-04|Computer code optimization method
    TWI602120B|2017-10-11|在圖案識別處理系統中用於電力管理之方法及系統
    JP4980834B2|2012-07-18|算術プロセッサ
    US4785400A|1988-11-15|Method for processing a data base
    EP0241946B1|1995-06-21|Information processing system
    KR101921373B1|2018-11-22|상태 기계 엔진들에 대한 결과들 생성
    US7451293B2|2008-11-11|Array of Boolean logic controlled processing elements with concurrent I/O processing and instruction sequencing
    US3614742A|1971-10-19|Automatic context switching in a multiprogrammed multiprocessor system
    US5465374A|1995-11-07|Processor for processing data string by byte-by-byte
    US4524416A|1985-06-18|Stack mechanism with the ability to dynamically alter the size of a stack in a data processing system
    US4641275A|1987-02-03|Vector processor having pair process mode and single process mode
    JP2015505399A|2015-02-19|状態機械格子におけるカウンタ動作
    US5644522A|1997-07-01|Method, apparatus and system for multiply rounding using redundant coded multiply result
    US6116768A|2000-09-12|Three input arithmetic logic unit with barrel rotator
    US5961635A|1999-10-05|Three input arithmetic logic unit with barrel rotator and mask generator
    JP2559399B2|1996-12-04|情報処理装置
    DE10124351B4|2005-10-27|Verfahren und Vorrichtung zum Verarbeiten zweier Datenoperanden in einem Prozessor
    US5487159A|1996-01-23|System for processing shift, mask, and merge operations in one instruction
    同族专利:
    公开号 | 公开日
    US5226135A|1993-07-06|
    引用文献:
    公开号 | 申请日 | 公开日 | 申请人 | 专利标题
    法律状态:
    1989-04-06| AK| Designated states|Kind code of ref document: A1 Designated state(s): JP US |
    优先权:
    申请号 | 申请日 | 专利标题
    [返回顶部]